Reverse 翻转链表

• 链表里最最经典的问题

206. Reverse Linked List

• 其实就是双指针prev, cur同步移动修改链表结构
• nxt指针暂存下一个指针的位置，最后prev到cur，cur到nxt

# Solution 1. Iteration
class Solution(object):
    def reverseList(self, head):
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

• 求n个node的情况，找n-1个node的情况如何拼起来
  • next->next = curr (subproblem head指向current node)
  • curr->next = null (current node's next is set to null)

# Solution 2. Recursion
class Solution(object):
    def reverseList(self, head):
        # Base Case
        if not head or not head.next:
            return head

        nhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return nhead

92. Reverse Linked List II

• 从位置m到位置n区间进行翻转
• 链表的操作需要像细心的医生，一根根的线要细心搭好
  • dummyNode是为了get the control of the first head

class Solution(object):
    def reverseBetween(self, head, m, n):
        if m == n: return head

        # Step1. Previous node of the start position
        dummyNode = ListNode(0)
        dummyNode.next = head
        start = dummyNode
        for _ in xrange(m-1):
            start = start.next

        # Step2. Reverse from n to m
        prev, cur = start.next, start.next.next
        for _ in xrange(n-m):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        # Step3. (Amazing Point of this question!)
        start.next.next = cur
        start.next = prev
        return dummyNode.next

24. Swap Nodes in Pairs

• 一两个指针为一块，保留当前块的previous指针和块后next指针

class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:
            return head

        dummyNode = ListNode(0)
        dummyNode.next = head
        prev, p1 = dummyNode, head
        while p1 and p1.next:
            p2 = p1.next
            nxt = p2.next

            prev.next = p2
            p2.next = p1
            p1.next = nxt

            prev = p1
            p1 = nxt
        return dummyNode.next

• Recursion 的解法看起来简练很多诶！

class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:
            return head
        p1 = head
        p2 = head.next
        nxt = self.swapPairs(p2.next)
        p1.next = nxt
        p2.next = p1
        return p2

25. Reverse Nodes in k-Group

• 算是Recursion的写法，Case 2 当中这个previous指针的赋值十分巧妙！正好需要翻转的链表第一个要连接的位置是后面链表的头！完美拼接！

class Solution(object):
    def reverseKGroup(self, head, k):
        if not head or not head.next:
            return head

        cur = head
        cnt = 0
        while cur and cnt < k:
            cur = cur.next
            cnt += 1

        # case 1 : less than k nodes
        if cnt < k:
            return head

        # case 2 : reverse the k nodes
        prev = self.reverseKGroup(cur, k)
        cur = head
        for _ in xrange(k):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev