Reverse Linked List

Algorithms
linked list, recursion
Catalogue
  1. 1. 206. Reverse Linked List
    1. 1.1. Iteration
    2. 1.2. Recursion
  2. 2. 92. Reverse Linked List II
  3. 3. 24. Swap Nodes in Pairs
    1. 3.1. Iteration
    2. 3.2. Recursion
  4. 4. 25. Reverse Nodes in k-Group
  5. 5. Convert a linked list
  6. 6. Print Linked List in reverse order
  • The most classic question in linked list

206. Reverse Linked List

Iteration

  • 其实就是双指针prev, cur同步移动修改链表结构
  • nxt指针暂存下一个指针的位置，最后prev到cur，cur到nxt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Iteration
# Time : O(n), Space : (1)
class Solution(object):
    def reverseList(self, head):
        prev, cur = None, head
        while cur:

            # Step1. Save the node, do not lost any control!
            nxt = cur.next

            # Step2. Modifying
            cur.next = prev

            # Step3. Iterative traverse next node
            prev = cur
            cur = nxt

        return prev

Recursion

  • 求n个node的情况，找n-1个node的情况如何拼起来
    • next->next = curr (subproblem head指向current node)
    • curr->next = null (current node’s next is set to null)
1
2
3
4
5
6
7
8
9
10
11
12
# Time : O(n), Space : (n)
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

  • Reverse Linked List only from position m to position n
  • 链表的操作需要像细心的医生，一根根的线要细心搭好
    • dummyNode => get the control of the first head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

Iteration

  • 4 pointers
  • 一两个指针为一块，保留当前块的previous指针和块后next指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

  • Only have to care about relation between n and n-2
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def swapPairs(self, head):
        # Base Case
        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指针的赋值十分巧妙！正好需要翻转的链表第一个要连接的位置是后面链表的头！完美拼接！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

Convert a linked list

N1->N2->N3->N4->N5->N6->….->Nn->null (convert to) N1->Nn->N2->Nn-1->….

  • Step1. Find the middle node of the linked List
  • Step2. reverse the 2nd half
  • Step3. Merge two linked list into one long

from Google Phone Interview

  • you can not modify the structure of linked list
  • can you do it in sublinear space complexity?
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# Time : O(n), Space : O(sqrt(n))
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

import math

class Solution(object):
    def PrintLinkedListInReverseOrder(self, head):
        if not head:
            return

        # Calculate the length
        length = 0
        cur = head
        while cur:
            cur = cur.next
            length += 1

        # Space : O(sqrt(n)
        n = int(math.sqrt(length))
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            for _ in range(n):
                if cur: cur = cur.next

        while stack:
            self.helper(stack.pop(), n)


    def helper(self, node, n):
        if not node or n == 0:
            return
        self.helper(node.next, n-1)
        print(node.val)
        return


node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

sol = Solution()
sol.PrintLinkedListInReverseOrder(node1)
Share