[剑指Offer] Day 12: Two Pointers

Authored by Tony Feng

Created on April 23rd, 2022

Last Modified on April 23rd, 2022

Task 1 - Q25. 合并两个排序的链表

Question

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution: # Recursion
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l2 or l1

        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution: # Iteration
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)

        pre = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next            
            pre = pre.next

        pre.next = l1 if l1 else l2

        return dummy.next

Explanation

Solution 1
- Time Complexity: O(M+N)
- Space Complexity: O(M+N)
Solution 2
- Time Complexity: O(M+N)
- Space Complexity: O(1)

Task 2 - Q52. 两个链表的第一个公共节点

Question

输入两个链表，找出它们的第一个公共节点。如果两个链表没有交点，返回 null。
要求：
- 在返回结果后，两个链表仍须保持原有的结构。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        '''
        1 -> 2 -> 3 -> 4 | 6 -> 3 -> 4
        6 -> 3 -> 4 | 1 -> 2 -> 3 -> 4
        '''
        tmpA, tmpB = headA, headB
        while tmpA != tmpB:
            tmpA = tmpA.next if tmpA else headB
            tmpB = tmpB.next if tmpB else headA

        return tmpA

Explanation

Time Complexity: O(M+N)
Space Complexity: O(1)