链表逆序

定义ListNode节点结构体

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x),next(NULL)
}

例题：
链表链接

int main(){
    ListNode a(10);
    ListNode b(20);
    ListNode c(30);
    ListNode d(40);
    ListNode e(50);

    a.next = & b;
    b.next = & c;
    c.next = & d;
    d.next = & e;
    ListNode *head = & a;
    while(head){
        print("%d %p %P\n,head->val, head,head->next");
        head = head->next
    }
    return 0;
    
}

LeetCode 206. Reverse Linked List

Eg1.链表逆序

一只链表头节点，指针head，将链表逆序。（不可申请额外空间）

链表数据结构

struct  ListNode{
int val;
ListNode  *next;
ListNode(int x) : val(x),next(NULL){}
};

打印head指针指向的链表

void print_list(ListNode * head,const char *List_name){
    printf("%S :",List_name);
    if(!head){
        printf("NULL\n");
        return;
    }
    while(head){
        printf("%d",head->val);
        head = head->next;
    }
    printf("\n");
}

1.构造5个节点a,b,c,d,e,并对它们进行初始化；
2.将a,b,c,d,e,5个节点连接在一起

int main(){
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;

    ListNode *head =&a;
    ListNode *new_head = NULL;
    LIstNode *next = NULL;
    print_list(head,"old");
    print_list(new_head,"new");
    return 0;


}

1、就地逆置法

1.备份head->next
2.修改head->next
3.移动head与new_head

class Solution{
public :
    ListNode *reverseList(ListNode * head){
    ListNode *new_head =NULL;//指向新链表头节点的指针
    while(head){
     ListNode * next = head->next;//备份head->next
     head->next = new_head; //更新head->next
     new_head = head_next; //移动new_head
     head = next;//遍历链表
     
}
return new_head;//返回新链表头节点
}
}

2、头插法

设置一个临时头节点temp_head,利用head指针遍历链表，每遍历一个节点即将该节点插入到temp_head后

1.备份next = head->next;
2.修改head->next
3.temp_head.next
4.移动head

class Solution{
public:
    ListNode * reverseList(ListNode * head){
    ListNode temp_head(0);
    while(head){
    ListNode *next = head->next;
    head->next = temp_head.next;
    temp_head.next = head;
    head =next;
}
    return temp_head.next;
}
}