经典链表问题：解析链表中的关键挑战

公共子节点

例如这样一道题：给定两个链表，找出它们的第一个公共节点。

具体的题目描述我们来看看牛客的一道题：

这里我们有四种解决办法：

采用集合或者哈希

思路是这样的，我们先把其中一个链表遍历放入Map中，然后遍历第二个第二个链表与Map中的对比，第一个相同的即为公共节点。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Map<ListNode, Integer>  map = new HashMap<>();
        while (pHead1 != null) {
            map.put(pHead1, pHead1.val);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            if (map.containsKey(pHead2)) {
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

采用栈

这种方法，我们需要两个栈把两个链表分别遍历入栈，然后同时弹出，相同且最晚出栈的那一组即为公共节点。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Stack<ListNode>  stack1 = new Stack<>();
        Stack<ListNode>  stack2 = new Stack<>();
        while (pHead1 != null) {
            stack1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            stack2.push(pHead2);
            pHead2 = pHead2.next;
        }
        ListNode ret = null;
        while (stack1.size() > 0 && stack2.size() > 0) {
            if (stack1.peek() == stack2.peek()) {
                ret = stack1.pop();
                stack2.pop();
            } else {
                break;
            }

        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

拼接两个字符串

先看下面的两个链表：
A：1-4-6-2-3-5
B：2-3-5
我们试着拼接一个
AB：1-4-6-2-3-5-2-3-5
BA：2-3-5-1-4-6-2-3-5
我们会发现链表只要有公共的节点，那么我们遍历AB与BA就会找到公共节点。

 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 =  pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            //防止陷入死循环
            if (p1 != p2) {
                if (p1 == null) {
                    p1 = pHead2;
                }
                if (p2 == null) {
                    p2 = pHead1;
                }
            }
        }
        return p1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

差和双指针

遍历两个链表记录两个链表的长度，然后先遍历较长链表（len1-len2）绝对值个节点，然后两个链表同时向前走，节点一样的时候就是公共节点。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        int len1 = 0, len2 = 0;
        while (p1 != null) {
            p1 = p1.next;
            len1++;
        }
        while (p2 != null) {
            p2 = p2.next;
            len2++;
        }
        int sub = Math.abs(len1 - len2);
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        if (len1 > len2) {
            int a = 0;
            while (a < sub) {
                current1 = current1.next;
                a++;
            }
        }
        if (len2 > len1) {
            int a = 0;
            while (a < sub) {
                current2 = current2.next;
                a++;
            }

        }
        while (current1 != current2) {
            current1 = current1.next;
            current2 = current2.next;
        }
        return current2;
    }
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

这段代码是一个Java方法，用于查找两个链表中的第一个公共节点。方法名为FindFirstCommonNode,接收两个参数pHead1和pHead2,分别表示两个链表的头节点。
首先，判断两个链表是否为空，如果有一个为空，则返回null。
然后，使用两个指针p1和p2分别遍历两个链表，计算它们的长度len1和len2。
接下来，计算两个链表长度之差的绝对值sub。
再接着，创建两个新的指针current1和current2,分别指向两个链表的头节点。如果链表1的长度大于链表2的长度，将current1向后移动sub个节点；如果链表2的长度大于链表1的长度，将current2向后移动sub个节点。
最后，同时遍历两个链表，直到找到第一个相同的节点，将其返回。

旋转链表

我们有两种思路：

• 将前k部分与N-k部分分别反转，连接起来就解决了。
• 用双指针找到倒数K的位置，具体实现如下：

  public ListNode rotateRight(ListNode head, int k) {
     if(head==null || k==0){
         return head;
     }
     ListNode fast = head;
     ListNode slow = head;
     ListNode temp = head;
     int len = 0;
     while (head!=null){
         head = head.next;
         len++;
     }
     if(k%len==0){
         return temp;
     }
     while (k%len>0){
         k--;
         fast = fast.next;
     }
     while (fast.next!=null){
         fast = fast.next;
         slow = slow.next;
     }
     ListNode res = slow.next;
     fast.next = temp;
     slow.next=null;
return res;
    }
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

1. 首先，判断链表是否为空或旋转位置数是否为0,如果满足任一条件，则直接返回原链表头节点。
2. 初始化三个指针：fast、slow和temp,都指向链表头节点。同时，定义一个变量len用于记录链表的长度。
3. 遍历链表，计算链表的长度。
4. 判断旋转位置数k是否能被链表长度整除，如果能整除，则不需要旋转，直接返回原链表头节点。
5. 如果旋转位置数k不能被链表长度整除，需要找到k对链表长度取模后的余数对应的节点位置。通过fast指针先向前移动k%len个位置，然后fast和slow指针同时向前移动，直到fast指针到达链表尾部。此时，slow指针所在的位置就是需要旋转后的新头节点。
6. 将新头节点的下一个节点作为新链表的尾节点，将原链表的尾节点接到新链表的头部，形成新的链表。
7. 返回新的链表头节点。