公共子节点
例如这样一道题：给定两个链表，找出它们的第一个公共节点。
具体的题目描述我们来看看牛客的一道题：
这里我们有四种解决办法：
采用集合或者哈希
思路是这样的，我们先把其中一个链表遍历放入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; }
- 首先，判断链表是否为空或旋转位置数是否为0,如果满足任一条件，则直接返回原链表头节点。
- 初始化三个指针：fast、slow和temp,都指向链表头节点。同时，定义一个变量len用于记录链表的长度。
- 遍历链表，计算链表的长度。
- 判断旋转位置数k是否能被链表长度整除，如果能整除，则不需要旋转，直接返回原链表头节点。
- 如果旋转位置数k不能被链表长度整除，需要找到k对链表长度取模后的余数对应的节点位置。通过fast指针先向前移动k%len个位置，然后fast和slow指针同时向前移动，直到fast指针到达链表尾部。此时，slow指针所在的位置就是需要旋转后的新头节点。
- 将新头节点的下一个节点作为新链表的尾节点，将原链表的尾节点接到新链表的头部，形成新的链表。
- 返回新的链表头节点。
