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

链表问题：解析链表中的关键挑战"/>

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

这里写目录标题

• 公共子节点
• • 采用集合或者哈希
  • 采用栈
  • 拼接两个字符串
  • 差和双指针
• 旋转链表

公共子节点

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

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

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

采用集合或者哈希

思路是这样的，我们先把其中一个链表遍历放入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;}

采用栈

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

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;}

拼接两个字符串

先看下面的两个链表：
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;}

差和双指针

遍历两个链表记录两个链表的长度，然后先遍历较长链表（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;}

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