剑指OfferJZ36：两个链表的第一个公共结点-java版

客官°小女子只卖身不卖艺 2022-09-09 13:52 110阅读 0赞

### 剑指OfferJZ36：两个链表的第一个公共结点-java版 ###

*   *   *   *  JZ36 两个链表的第一个公共结点

#### JZ36 两个链表的第一个公共结点 ####

**描述**  
输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）  
示例1

> **输入：**  
> \{1,2,3\},\{4,5\},\{6,7\}  
> 返回值：  
> \{6,7\}

**说明：**  
第一个参数\{1,2,3\}代表是第一个链表非公共部分，第二个参数\{4,5\}代表是第二个链表非公共部分，最后的\{6,7\}表示的是2个链表的公共部分  
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的  
示例2

> **输入：**  
> \{1\},\{2,3\},\{\}  
> 返回值：  
> \{\}

说明：  
2个链表没有公共节点 ,返回null，后台打印\{\}

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16]

题目的意思是让我们找到比如上图两个单链表的第一个公共节点  
**解法一：**  
思路是**从链表的尾部开始遍历（反向遍历）**，如果碰到有不一样节点的地方，就返回到上一次遍历的节点位置，这个节点就是两个链表的第一个公共节点

> 我们可以设置链表一从后往前遍历的节点为node1，链表二从后往前遍历的节点为node2，判断node1和node1这两个节点是否一样，
> 
> 如果一样就说明当前位置的节点是公共节点，  
> 如果不一样说明不是，那么上一次的节点就是我们要找的第一个公共节点

那么还有个问题，遍历单链表时只能从前往后遍历，**如何反向遍历单链表**呢？  
我们可以使用**栈**，利用栈Stack先进先出的特质：  
将链表放入栈中，然后拿出来，从栈中拿出数据的过程正好是我们想要的反向遍历  
比如把：1 2 3 4 5 6 7放入栈，拿出来就是7 6 5 4 3 2 1

public class jz36 { 
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
            //定义两个栈
            Stack<ListNode> stack1 = new Stack<>();
            Stack<ListNode> stack2 = new Stack<>();
    
            //将两个链表分别放入栈中
            while(pHead1!=null){ 
                stack1.add(pHead1);
                pHead1=pHead1.next;
            }
            while(pHead2!=null){ 
                stack2.add(pHead2);
                pHead2=pHead2.next;
            }
    
            ListNode ans=null;//存放两个链表的公共节点
            //peek()函数返回栈顶的元素，但不弹出该栈顶元素
            //pop()函数返回栈顶的元素，并且将该栈顶元素出栈
            while(!stack1.isEmpty() && !stack2.isEmpty()){ 
                if(stack1.peek().val==stack2.peek().val){ //说明当前节点是两个链表的公共节点
                    ans=stack1.peek();//将公共节点存入ans中
                    stack1.pop();
                    stack2.pop();
                }else{ //两个链表的节点不相等，此时上面ans里存放的值就是第一个公共节点
                    break;
                }
            }
            return ans;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**解法二：**  
解法一另外开辟了两个栈空间，有些占用空间  
现在不用另外开辟空间的思路是：

*  首先**计算出两个链表的长度**
 *  如果**长度相同**，就从前往后同时同步遍历两个链表，直到某个位置两个链表的节点值相同时，这个节点就是这两个单链表的第一个公共节点
 *  如果**长度不同**，就先遍历长的那个链表，让该链表的头节点先向后移动若干位，直到两个节点的长度相同为止，然后我们就可以如上同时遍历链表找公共节点了

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 2]

public class jz36 { 
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {    
            //法二：
            int len1=0;
            int len2=0;
    
            //统计两个链表的长度
            ListNode removeNode1=pHead1;
            ListNode removeNode2=pHead2;
            while(removeNode1!=null){ 
                len1++;
                removeNode1=removeNode1.next;
            }
            while(removeNode2!=null){ 
                len2++;
                removeNode2=removeNode2.next;
            }
    
            //使两个链表长度相同
            if(len1>len2){ 
                for(int i=1;i<=len1-len2;i++){ 
                    pHead1=pHead1.next;
                }
            }else if(len1<len2){ 
                for(int i=1;i<=len2-len2;i++){ 
                    pHead2=pHead2.next;
                }
            }
    
            //同时同步遍历链表，找第一个公共节点
            ListNode ans=null;//存放两个链表的公共节点
            while(pHead1!=null){ //这里亦可以写pHead2!=null，都一样
                if(pHead1.val==pHead2.val){ 
                    ans=pHead1;//也可以写ans=pHead2;
                    break;
                }
                pHead1=pHead1.next;
                pHead2=pHead2.next;
            }
            return ans;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 3]

![在这里插入图片描述][2ebc2a572160461ca89a04c3d8d729fb.gif_pic_center]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/1f637373466c4fb9b80d47f561696fe3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/facb4dacc71e4f868b30e69b28ff1e89.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/96168b5b7ee24c51b180e79dce3907e9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/40e901015c044b7f9d3303e7b0a9542e.png
[2ebc2a572160461ca89a04c3d8d729fb.gif_pic_center]: /images/20220829/c8f16e21c0524a158ef3ef8804f7b819.png