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

落日映苍穹つ 2024-02-21 10:38 64阅读 0赞

#### 这里写目录标题 ####

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

## 公共子节点 ##

例如这样一道题：给定两个链表，找出它们的第一个公共节点。  
![在这里插入图片描述][bbe86fd701944517849b35446bb4e6d8.png]  
具体的题目描述我们来看看[牛客的一道题][Link 1]：  
![在这里插入图片描述][bc243fba11d54fcf8640767a59bbd67c.png]  
这里我们有四种解决办法：

### 采用集合或者哈希 ###

思路是这样的，我们先把其中一个链表遍历放入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.  返回新的链表头节点。

[bbe86fd701944517849b35446bb4e6d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/169cceb529574b0b9ec62d6b9f55cafe.png
[Link 1]: https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&ru=/exam/oj
[bc243fba11d54fcf8640767a59bbd67c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/da31aad36b8742c4b2edd42e02009189.png