[剑指Offer] Day 2: Linked List

Authored by Tony Feng

Created on April 13th, 2022

Last Modified on April 13th, 2022

Task 1 - Q06. 从尾到头打印链表

Question

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution: # Iteration
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []

        res = []
        while head:
            res.append(head.val)
            head = head.next

        return res[::-1]

Solution 2

1
2
3
4
5
6


class Solution: # Recursion
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        else:
            return self.reversePrint(head.next) + [head.val]

Explanation

Solution1 & Solution2
- Time Complexity: O(N)
- Space Complexity: O(N)

Task 2 - Q24. 反转链表

Question

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

Solution 1

1
2
3
4
5
6
7
8
9


class Solution: # Two Pointers
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            tmp = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = tmp      # cur 访问下一节点
        return pre   

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution: # Recursion
    def reverseList(self, head: ListNode) -> ListNode:
        
        if not head or not head.next:
            return head

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

Explanation

Solution1
- Time Complexity: O(N)
- Space Complexity: O(1)
Solution2
- Time Complexity: O(N)
- Space Complexity: O(N)

Task 3 - Q35. 复杂链表的复制

Question

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

Solution

 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


class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head

        node_dict = {}
        cur = head
        # Traverse the origin nodes and put them in a dictionary
        while cur:
            # Mapping the original node to a new node
            # Only val is updated here
            node_dict[cur] = Node(x=cur.val) 
            cur = cur.next
        node_dict[cur] = None

        # Traverse the dictionary and update the next and random pointer
        cur = head
        while cur:
            node_dict[cur].next = node_dict[cur.next]
            node_dict[cur].random = node_dict[cur.random]
            cur = cur.next

        # Return the head of the new linked list
        return node_dict[head]  

Explanation

Steps
- Use a dictionary to record the position of the original nodes
- Update the next and random pointer in reference to the original nodes
Time Complexity: O(N)
Space Complexity: O(N)