算法笔记-链表

Algorithm › Data Structure › LinkList

See code in Git Repository/Leetcode-algorithm/data_structure/Linked_list

Most in Link_List_Review.py

链表的环

判断是否有环：

  • 维护快慢两个指针， 快指针一次前进两位，慢指针一次一位。 若两个指针能够相遇，则有环。 若快指针运动到末尾还未与满指针相遇则无环。
  • 注意， 如果有环，则使用 while node.next is not None为判断条件时，一定会有快慢指针相遇的时候， 因为如果有环的话， 那么链表就没有尾节点，也就是没有next为None的节点。换句话说， 如果链表有尾节点，也就是next 为none的节点，那么链表一定无环。

More in Detail update at 16/04/2023

1
2
3
4
5
6
7
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) {
       return true;
    }
}

快慢指针同向奔跑， fast 的速度是slow的一倍， 如果有环， 那么两者必定在某一点相遇， 也即fast会追上slow， 此时fast正好比slow多走了一圈的路程。

找到链表环的入口：

  • 首先使用上述方法判断是否有环
  • 找到环中任意一个节点。
    • 方法： 若有环， 则使用上述方法判断过程中会得到两个指针相遇的节点。
  • 当快慢指针相遇时，创建一新指针从头节点出发， 当该新指针与慢指针相遇时所处的结点即为环的入口。

More in Detail update at 16/04/2023

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 若链表无环， 则fast会走到链表结尾， 而此时slow还在链表中间。
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) {
        slow = head;
        break;
    }
}

// 如果链表中没有环， 该while condition 中的前两个条件会跳过该while， 直接return。
while (fast != null && fast.next != null && slow != fast) {
    slow = slow.next;
    fast = fast.next;
}

// 如果fast为null 或者fast.next为null， 代表链表无环
return fast == null || fast.next == null? null: slow;

Explaination

slow 路程 = x + y; fast 路程 = x + y + n(y + z)

由于 fast = 2 slow:

2(x+y) = x+y + n (y+z)；

x + y = n (y + z)

x = (n-1) y + nz

其中n为fast在环中跑的圈数。在相遇时， fast指针最少在环中已经跑了一圈， 所以 n >=1。

假设 n = 1， 则得 x=z, 也即当slow&fast相遇以后， 使得slow在head开始跑， fast在meeting point开始跑， 则两者必定在entry poin相遇。

笔记 2023年4月15日

相交链表

使pA， pB两个指针分别从headA和headB出发， 当pA跑完了A链以后， 使其从B链头节点继续跑， pB 同理。

当pA=pB时， 要么两者相遇在相交节点， 要么两者同时跑到链表结尾， 即 null = null。

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA;
    ListNode pB = headB;

    while (pA != pB) {
        pA = pA == null? headB: pA.next;
        pB = pB ==null? headA: pB.next;
    }
		
  	// 若没有交点， while将在pA = pB = null 时退出循环
    return pA;
}

Explanation

当P1 第二次经过交点 I 时， 其走过的距离 = (M + N) + Z;

同理， 当P2 第二次经过交点时， 其走过的距离 = (N + Z ) + M;

两者相等。所以只要有交点， P1 & P2 必相交于交点处。

链表-2

若两条链没有交点， 假设 ListA = X, ListB = Y.

则当P1 遍历完两条链走到null 时， 其路程为 X + Y。 同理， P2的路程为Y + X。 所以只要两条链表没有相交， 两者必在 null 处相遇。

链表的倒数第K个元素 - offer

  • 注意双指针在链表中的使用：
    • 倒数第k个元素， 可使快指针先走k步， 然后慢指针再开始走，这样当快指针走到末尾慢指针所指即答案。
  • 注意代码鲁棒性：
    • 所谓鲁棒性即注意对input的检查， 通常再写算法时表现再程序入口的几个 if-return。 很重要，勿忘。
    • 再此题中包括：
      • 链表是否为空？
      • k是否为0？
      • 链表长度是否大于k？

链表的反转

  • recursive即可

  • 但是注意：

    • 不要忘了把原头节点的next置空
    • 终止条件应为：
    1
    2
    3
    4
    5
    6
    7
    """
    不应使用cur_node is None 为if条件，因为不好记录新的头节点
    """
    if cur_node.next is None:
        cur_node.next = pre_node
        self.head = cur_node
        return