反转单向链表

一、题目详情

题目连接

leetcode反转链表

题目内容

Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
1
2

Example 2:

Input: head = [1,2]
Output: [2,1]
1
2

Example 3:

Input: head = []
Output: []
1
2

Constraints:

The number of nodes in the list is the range [0, 5000].
 5000 <= Node.val <= 5000
1
2

Follow up:

 A linked list can be reversed either iteratively or recursively.
  Could you implement both?
1
2

二、题目详解

1、逻辑

我们想要反转一个链表，那么在物理结构上的本质就是将某节点的指针域从记录后一个节点的地址改为记录前一个节点的地址。
那么在这个过程中有以下几个问题：

• 我们如何得知前面一个节点的地址？
• 某个节点反转后会造成后一节点的地址丢失，如何解决？

2、图解

我们创建三个指针，n2指针是我们需要反转的节点对象，n1是前一个节点的地址，n3是后一个节点的地址。n2是核心，n1,n3起到临时记录的作用。

但是我们需要考虑特殊情况：

• 空链表
  这种情况是不需要反转的，直接返回结果即可。

/*
 * Definition for singly-linked list.
 * struct ListNode 
 * {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return head;
    }
    
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    struct ListNode*n3=head->next;
    while(n2!=NULL)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3!=NULL)
        n3=n3->next;//考虑n3是空指针
    }
    return n1;
}
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

三、其他方法

1、四指针

这个方法其实和上面的方法非常相似，只是这一种方法可能更好理解逻辑。上面的两个n1,n2指针负责记录节点位置，下面的两个红色指针负责逆转链表。这种方法同样需要考虑刚刚提到特殊情况。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return head;
    }
    
    struct ListNode*n1=head;
    struct ListNode*n2=head->next;
    struct ListNode*after_n1=NULL;
    struct ListNode*after_n2=n1;
    while(n1!=NULL)
    {
        after_n2->next=after_n1;
        after_n2=n2;
        after_n1=n1;
        n1=n2;
        if(n2!=NULL)
        n2=n2->next;
    }
    return after_n1;

}
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
29
30
31

2、头插

（1）图示

（2）代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return head;
    }
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    struct ListNode* nex=cur->next;
    while(cur!=NULL)
    {
        cur->next=newhead;
        newhead=cur;
        cur=nex;
        if(nex!=NULL)
        nex=nex->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