206. 反转链表

一、题目描述

转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

二、解题思路 & 代码

2.1 双指针迭代

我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

class Solution(object):
	def reverseList(self, head):
		""" :type head: ListNode :rtype: ListNode """
		# 申请两个节点，pre和 cur，pre指向None
		pre = None
		cur = head
		# 遍历链表，while循环里面的内容其实可以写成一行
		# 这里只做演示，就不搞那么骚气的写法了
		while cur:
			# 记录当前节点的下一个节点
			tmp = cur.next
			# 然后将当前节点指向pre
			cur.next = pre
			# pre和cur节点都前进一位
			pre = cur
			cur = tmp
		return pre

2.2 递归解法（比较难理解）

这题有个很骚气的递归解法，递归解法很不好理解，这里最好配合代码和动画一起理解。
递归的两个条件：

  1. 终止条件是当前节点或者下一个节点==null
  2. 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句 
head.next.next = head

很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

class Solution(object):
	def reverseList(self, head):
		""" :type head: ListNode :rtype: ListNode """
		# 递归终止条件是当前为空，或者下一个节点为空
		if(head==None or head.next==None):
			return head
		# 这里的cur就是最后一个节点
		cur = self.reverseList(head.next)
		# 这里请配合动画演示理解
		# 如果链表是 1->2->3->4->5，那么此时的cur就是5
		# 而head是4，head的下一个是5，下下一个是空
		# 所以head.next.next 就是5->4
		head.next.next = head
		# 防止链表循环，需要将head.next设置为空
		head.next = None
		# 每层递归函数都返回cur，也就是最后一个节点
		return cur

参考：

  1. LeetCode题解

========================================================

========================================================

92. 反转链表 II

一、题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

二、解题思路 & 代码

2.1 递归解法

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

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # base case
        if m==1:
            # 相当于反转前 n 个元素
            last = self.reverseN(head,n)
            return last
        # 前进到反转的起点触发 base case
        head.next = self.reverseBetween(head.next,m-1,n-1)
        # print(head)
        return head
    # 将链表的前 n 个节点反转（n <= 链表长度）
    # 反转以 head 为起点的 n 个节点，返回新的头结点
    def reverseN(self, head: ListNode, n: int):
        if n==1:
            return head
        # 以 head.next 为起点，需要反转前 n - 1 个节点
        last = self.reverseN(head.next,n-1)
        successor = head.next.next
        head.next.next = head
        # 让反转之后的 head 节点和后面的节点连起来
        head.next = successor
        return last
  1. 时间复杂度都是 O(N)
  2. 空间复杂度 O(N) ，因为递归解法需要堆栈

参考：
LeetCodet题解

2.2 迭代解法

class Solution:
    def reverseBetween(self, head, m, n):
        # Empty list
        if not head:
            return None

        # Move the two pointers until they reach the proper starting point
        # in the list.
        cur, prev = head, None
        while m > 1:
            prev = cur
            cur = cur.next
            m, n = m - 1, n - 1

        # The two pointers that will fix the final connections.
        tail, con = cur, prev

        # Iteratively reverse the nodes until n becomes 0.
        while n:
            third = cur.next
            cur.next = prev
            prev = cur
            cur = third
            n -= 1

        # Adjust the final connections as explained in the algorithm
        if con:
            con.next = prev
        else:
            head = prev
        tail.next = cur
        return head
  1. 时间复杂度: O(N)。考虑包含 N 个结点的链表。对每个节点最多会处理
    （第 n 个结点之后的结点不处理）。
  2. 空间复杂度: O(1)。我们仅仅在原有链表的基础上调整了一些指针，只使用了 O(1) 的额外存储空间来获得结果。

参考：
LeetCode官方题解