2019-04-12 10:10:02 青峰科技

LeetCode 206 反转链表

我们首先看一下题目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

这道题目是反转链表，那么先说一下常规思维是怎样的

方法1：就地反转法

2.1 思路

把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中，就地反转。

dummy->1->2->3->4->5的就地反转过程：

dummy->2->1->3->4->5

dummy->3->2->1->4->5

dummy->4>-3->2->1->5

dummy->5->4->3->2->1

2.2 解释

1初始状态

2 过程

pCur是需要反转的节点。

prev连接下一次需要反转的节点
反转节点pCur
纠正头结点dummy的指向
pCur指向下一次要反转的节点

伪代码

1 prev.next = pCur.next;
2 pCur.next = dummy.next;
3 dummy.next = pCur;
4 pCur = prev.next;

3 循环条件

pCur is not null

2.3 代码

 1 // 1.就地反转法
 2 public ListNode reverseList1(ListNode head) {
 3 if (head == null)
 4 return head;
 5 ListNode dummy = new ListNode(-1);
 6 dummy.next = head;
 7 ListNode prev = dummy.next;
 8 ListNode pCur = prev.next;
 9 while (pCur != null) {
10 prev.next = pCur.next;
11 pCur.next = dummy.next;
12 dummy.next = pCur;
13 pCur = prev.next;
14 }
15 return dummy.next;
16 }

2.4 总结

1个头结点，2个指针，4行代码
注意初始状态和结束状态，体会中间的图解过程。

3 方法2：新建链表，头节点插入法

3.1 思路

新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。

3.2 解释

1 初始状态

2 过程

pCur是要插入到新链表的节点。

pNex是临时保存的pCur的next。

pNex保存下一次要插入的节点
把pCur插入到dummy中
纠正头结点dummy的指向
pCur指向下一次要插入的节点

伪代码

1 pNex = pCur.next
2 pCur.next = dummy.next
3 dummy.next = pCur
4 pCur = pNex

3 循环条件

pCur is not null

3.3 代码

 1 // 2.新建链表,头节点插入法
 2 public ListNode reverseList2(ListNode head) {
 3 ListNode dummy = new ListNode(-1);
 4 ListNode pCur = head;
 5 while (pCur != null) {
 6 ListNode pNex = pCur.next;
 7 pCur.next = dummy.next;
 8 dummy.next = pCur;
 9 pCur = pNex;
10 }
11 return dummy.next;
12 }l

可见，逻辑非常复杂，下面我们要讲一个简单方法，递归反转法

如何递归反转哪？假设有2个节点，只需要将第二个节点指向第一个，链表头指向第二个节点即可。

那么试想一下，假设将剩下的节点，都看成第一个节点那么问题就简单了

直接上代码吧

class Solution {
public:
 ListNode *we;
 ListNode *reverseList(ListNode *head) {
 if (head== nullptr||head->next== nullptr)
 {
 return head;
 }
 ListNode *p = head;
 ListNode *l = head->next;
 reverce(l, p);
 head->next = nullptr;
 return we;
 }
 void reverce(ListNode *l, ListNode *p) {
 if (l->next != nullptr) {
 reverce(l->next, p->next);
 } else
 {
 we = l;
 }
 l->next = p; 

 }
};