反转链表_reverselist(struct listnode* head)

反转一个单链表

法一：利用3个指针

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
    while(n2)  //直到n2为空结束循坏
    {
        //翻转
        n2->next = n1;

        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)
             n3 = n3->next;
    }
    return n1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

法二：头插法，不创建结点
整体思路：取原链表中的结点头插到新结点，要先保存当前结点的下一个地址，不然取结点后找不到后面的结点。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct LidtNode* newHead = NULL;
    while(cur)
    {
        struct ListNode* next = NULL;  //此句话和下一句可合成： struct ListNode* next = cur->next;
        next = cur->next;  //保存下一结点的地址
        cur->next = newHead;  //指向新结点
        newHead = cur;   //
        cur = next;
    }
    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

有问题代码（自己犯的错误）：

//2.头插法，不创建新结点
//整体思路：取原链表中的结点头插到新结点，要先保存一个结点的下一个地址，不然取结点后找不到后面的结点
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct LidtNode* newHead = NULL;
    while(cur)
    {
        //next是为了保存一份cur->next的地址，为了后面赋给cur,再循环头插
        struct ListNode* next = NULL;  //此句话和下一句可合成： struct ListNode* next = cur->next;
        next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;

    //有问题代码  //cur->next指向的是newHead,改变了指向的对象
    //     struct ListNode* cur = head;
    //     struct ListNode* newHead = NULL;
	//     while (cur)
  	// {
	//         cur->next = newHead;
	//     	newHead = cur;

	// 	    cur = cur->next;
	//     }
    //  	return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28