【LeetCode】206、反转链表

206、Reverse Linked List反转链表

难度：简单

题目描述

• 英文：

  Reverse a singly linked list.

• 中文：

  反转一个单链表。

• 示例

  Example:

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

• 进阶
  你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

递归解决方法的视频讲解

Reverse a Linked List Recursively

思路一

参考讨论区的一种做法。

时间复杂度O(N)，空间复杂度O(1)

这里给出两种方法：迭代法（循环），递归方法。

两种方法的思路都是一样的。如下所示

…<-x<-x<-x<-x<-pre || cur->y->y->y->y…

1. 将整个链表分成两个部分；前半部分链表，后半部分链表
2. pre为已经 反转 好的部分链表的头节点；
3. cur为当前仍然没有反转部分链表的头节点；
4. 我们当前需要做的事情就是将cur节点加入到前半部分的链表中，
   直到右边的链表全部加入到左边的链表中即可。
5. 用递归的思想理解4很容易。

代码提交

递归方法

C++，用时8ms，内存9M

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if (cur->next == NULL) { // 递归结束的判断
            cur->next = pre;
            return cur;
        }
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
        return reverse(pre, cur);
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL, *cur = head;
        return head ? reverse(pre, cur) : head; // 如果head为空的话，我们直接返回head/NULL
    }
};

迭代方法

C++，用时8ms，内存9.1M

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode* pre = NULL, *cur = head, *next = head->next;
        while (cur->next) {
            cur->next = pre;
            pre = cur;
            cur = next;
            next = next->next;
        }
        cur->next = pre;
        return cur;
    }
};

思路二

参考LeetCode上递归探索页给出的解决方案。

递归版，是从后往前来转变链表指针的方向；迭代版是从前往后来转变链表的方向。

代码提交

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 递归版
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    // 迭代版
    public ListNode reverseList1(ListNode head) {
        if (head != null){
            ListNode p1 = null;
            ListNode next = null;
            ListNode p2 = head;
            while (p2 != null){
                next = p2.next;
                p2.next = p1;
                p1 = p2;
                p2 = next;
            }
            return p1;
        }else {
            return head;
        }
    }   
}

思路三

参考网上的解法，巧妙利用Python的多元赋值，实现非常简洁。

具体的执行过程可参考下面的举例说明：

前置条件：迭代指针：p = head、结果指针：res = none

以1->2->3->4->5为例：

过程：

res:None

第一层循环

res:1->2->3->4->5 res = p

res:1->None res.next = res

p:2->3->4->5 p = p.next

第二层循环

res:2->3->4->5 res = p

res:2->1->None res.next = res

p:3->4->5 p = p.next

第三层循环

res:3->4->5 res = p

res:3->2->1->None res.next = res

p:4->5 p = p.next

第四层循环

res:4->5 res = p

res:4->3->2->1->None res.next = res

p:5 p = p.next

第五层循环

res:5 res = p

res:5->4->3->2->1->None res.next = res

p:None p = p.next

end…

代码提交

Python，用时32ms，内存12.7M

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        L = ListNode(float("-inf"))
        while head:
            # 把当前 L.next （如 [2,1]）内容临时保存起来，然后把head此时剩下的内容（如 [3,4,5]）赋给L （变成[3,4,5]），再把之前保存的L.next接回来（L变成[3,2,1]），最后head后移一步
            L.next, head.next, head = head, L.next, head.next
        return L.next