大家好,我是bug郭,一名双非科班的在校大学生。对C/JAVA、数据结构、Spring系列框架、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN java领域新星创作者blog.csdn.net/bug…
• 掘金LV3用户 juejin.cn/user/bug…
• 阿里云社区专家博主,星级博主,developer.aliyun.com/bug…
• 华为云云享专家 bbs.huaweicloud.com/bug…

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

题目链接: 两个链表的第一个公共结点

题目分析:

• 可以直接先遍历一遍计算2个链表长度的差值,然后再让一个链表遍历到差值位,然后同时遍历,比较节点是否相同!!!
• 通过两个指针速度相同,走过的路程相同必会相遇!
• cur1 走完 L1,cur1指向 L2,cur2走完L2,指向L1!

差值法
java

//先计算长度差,然后让一个指针先走差值单位!
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            ListNode cur1 = pHead1;
            ListNode cur2 = pHead2;
        int size1 = 0;
        int size2 = 0;
        while(cur1!=null){
            cur1 = cur1.next;
            size1++;
        }
        while(cur2!=null){
            cur2 = cur2.next;
            size2++;
        }
        if(size1>size2){
            int len = size1 - size2;
            while(len-->0){
                pHead1 = pHead1.next;
            }
        }else{
             int len = size2 - size1;
            while(len-->0){
                pHead2 = pHead2.next;
            }
        }
         
        while(pHead1!=null){
            if(pHead1.val==pHead2.val){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}

python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        len1=len2 = 0
        cur1,cur2 = pHead1,pHead2
        while cur1:
            len1+=1
            cur1 = cur1.next
        while cur2:
            len2 +=1
            cur2 = cur2.next
        # 这里还要判断那个链表的长度更长...
        # 我们默认设置为cur1链表更长!
        size = 0
        if len1>len2:
            size = len1 - len2
            cur1 = pHead1
            cur2 = pHead2
        else:
            size = len2 - len1
            cur1 = pHead2
            cur2 = pHead1
        while size:
            cur1 = cur1.next
            size -= 1
        #遍历2个链表比较!
        while cur1 and cur2:
            if cur1 == cur2:
                return cur1
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1

相同路程法
操作如图所示

java

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            //定义2个指针! 
            // cur1 走完 L1,又从 L2开始!
            // cur2 走完 L2,又从 L1开始!
            // 这里两个指针速度相同,走过的长度相等,如果有相同节点肯定相遇!
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1!=cur2){//不存在公共节点,两个指针会来到null相等退出循环!
            cur1 = (cur1==null) ? pHead2 : cur1.next;
            cur2 = (cur2 == null) ? pHead1 : cur2.next;
        }
        return cur1;
    }
}

python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        a = pHead1
        b = pHead2
        while a!=b:
            a = a.next if a else pHead2
            b = b.next if b else pHead1
        return a 

链表中环的入口结点

题目链接: 链表中环的入口结点

题目分析:

• 可以通过哈希表保存节点,然后遇到重复节点,就是环入口节点,但是这里要求空间复杂度为O(n),所以并不行…
• 我们可以通过快慢指针!先找到快慢指针的相遇位置,有环必相遇.fast走2步,slow走1步!
• 找到相遇点后,然后让一个指针从头节点出发,另一个节点在相遇位置出发,他们相遇点就是环入口!
  

题目解答:
java

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快慢指针,利用链表头到入口距离 = 相遇点到入口距离!
        //所以当两个节点相遇后再走L距离就是入口位置!
        //相遇后让其中一个指针从链头开始走L,一个从相遇点开始!
        ListNode slow = pHead,fast = pHead;
        while(fast!=null&&fast.next!=null){//注意判断条件!!!!
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                //相遇!
                //让slow从头结点开始!
                slow = pHead;
                while(fast!=slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast = slow = pHead
        # 快慢指针!
        # fast走的路程是slow的2倍,设圆弧长:C,头节点到环入口为:L,相遇点理入口环距离:X
        # 根据路程关系: L+C+X = 2*(L+X) -> L+C+X = 2L+2X  C = L+X -> L = C-X
        # 所以相遇点到环入口等于L长度!
        while fast!=None and fast.next!=None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                # 相遇!
                fast = pHead
                while fast!=slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None