LinkedList Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class ListNode {
    // 结点值
    int val;
    // 下一个结点
    ListNode next;
    
    // 无参构造
    public ListNode() {
    }
    
    // 有参构造
    public ListNode(int val) {
        this.val = val;
    }
    
    // 全参构造
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

LinkedList Operate

insert

// 注意: 头结点 -> 建议增加虚拟头结点进行处理

1
2
3
cur.val = target;
newNode.next = cur.next;
cur.next = newNode;

delete

// 注意: 头结点 -> 建议增加虚拟头结点进行处理

1
2
cur.next.val = target;
cur.next = cur.next.next;

160.链表相交

[链表相交](面试题 02.07. 链表相交 - 力扣（LeetCode）)

image-20240819210334517

第一眼看到这个题目，很快啊就能想到分别遍历得到长度然后长的前进差值的步数,然后根据node1==node2来结束。但是呢，还有一个巧妙的方式是两个链表同步前进，短的走完后呢，开始从长的头部开始同步向后走，当长的走完后呢，开始从短的头部开始同步往后走，此时！此时！他们到链表尾部的长度是相同的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// p1 指向 A 链表头结点，p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 链表末尾，转到 B 链表
			if (p1 == null) p1 = headB;
			else            p1 = p1.next;
			// p2 走一步，如果走到 B 链表末尾，转到 A 链表
			if (p2 == null) p2 = headA;
			else            p2 = p2.next;
		}
		return p1;
    }
}

142.环形链表II

[142.环形链表II](142. 环形链表 II - 力扣（LeetCode）)

image-20240819212037291

看到这个题目呢，第一眼…没思路，哈哈。第二眼，si~，一个指针求不了，双指针？双指针两个指针之间也没有固定的长度呀。又不会了~

那么想不出来哈哈瞄一眼答案🧐 果然-双指针! 再看一眼，哇！学到了

既然不知道双指针之间的长度，但是但是这个题目要求有没有环呀，既然如此那一个走快点一个走慢点，如果有环，岂不是必相遇。

那么快指针走两步，慢指针走一步，如果相遇那么 有环！

下一个难题：环的入口怎么确定呢？？？

如果相遇，那么2(x+y)=x+n(y+z)+y2(x+y)=x+n(y+z)+y，化简一下

x=(n−1)(y+z)+zx=(n-1)(y+z)+z

可以发现！从头出发一步一步走|从相遇点出发一步一步走 那么入口相遇！这不，完美解决🛫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}