(Java数据结构)链表题

系统管理员 2024-04-06 10:34 71阅读 0赞

#### 文章目录 ####

*  环形链表
 *   *  判断链表中是否有环
     *  找到链表开始入环的第一个节点
 *  链表分割

## 环形链表 ##

### 判断链表中是否有环 ###

leetcode
    141. 环形链表

![在这里插入图片描述][ff7364d240d448059d3d56051c18cd23.png]

> 类似追及相遇问题，定义快慢指针，如果没有环，快指针会走到null；如果有环，快慢指针肯定会在环中相遇。  
> 问题来了，慢指针一次走一步，那快指针应该一次走2步？还是走3步？走4步？

> 如果每次快指针走2步，慢指针走1步，最坏的情况下，慢指针刚入环时，快指针比慢指针多走一个环的路程，因为每次快指针比慢指针多走1步，所以在慢指针还没走到一圈时，快指针一定可以追上慢指针![在这里插入图片描述][ecdb8fb7eadb4a039a5be2df2ac95ee3.png]

> 如果环中只有两个节点这种情况，如果快指针每次走3步，慢指针每次走1步，那么快慢指针永远不能相遇  
> ![在这里插入图片描述][9235d7a01710452688fd3764533b527a.png]

> 所以将快指针设置为每次走2步，慢指针每次走1步，两个指针在环中一定能相遇。如果慢指针走1步，快指针走3/4/5…步，两个指针有可能不会相遇。

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
        
                slow=slow.next;
                fast=fast.next.next;
                if(fast==slow){
        
                    return true;
                }
            }
            return false;
        }
    }

### 找到链表开始入环的第一个节点 ###

leetcode
    142. 环形链表 II

![在这里插入图片描述][3fbbcff71c71420d8c42158c29fc750f.png]

> 设从链表起始位置到入环点距离是X，环的长度是C，相遇点到入环点距离是Y，入环点到相遇点距离是C-Y

> 假设快指针比慢指针多走N圈时相遇，即慢指针走了X+C-Y，快指针走了X+C-Y+N*C，因为快指针速度是慢指针的2倍，所以相同时间内，快指针走的距离是慢指针的2倍，即X+C-Y+N*C=2\*(X+C-Y)，解得X-Y=(N-1)\*C.  
> 当N=1时，X=Y  
> 那么可以在链表起始点定义一个指针p1，在相遇点定义一个p2，两个指针每次走1步，最后在入环点相遇。  
> 当N=2时，p2要走Y+C两个指针才能在入环点相遇，当N>2时两个指针最后也总能相遇，只是时间变长

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
        
                slow=slow.next;
                fast=fast.next.next;
                if(fast==slow){
        
                    slow=head;
                    while(slow!=fast){
        
                        slow=slow.next;
                        fast=fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }

## 链表分割 ##

牛客网
    CM11 链表分割
    现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

![在这里插入图片描述][0919bdf31cef4690acda66c32e4a7bdf.png]

> 举例：以30为界限分割两块区域，<30的区域，>30的区域，  
> <30的区域定义2个指针bs，be。>30的区域定义2个指针as，ae。再定义一个cur指针，指向链表的头结点，遍历链表。如果cur.val<30，那么cur所指的结点就放在<30的区域。当有第2个元素放到<30的区域时，be往后走。直到cur走到null为止，然后be.next=as，前后两个区域的结点连接起来。

> 此处有坑：①如果所有元素都是>30的，那么be一直为null，如果be.next会报错空指针异常。②如果ae所指的尾结点不是原链表中的尾结点，即ae.next!=null，那么会导致链表死循环，所以需要我们手动将ae.next=null置空。③这样又会出现新的问题，如果as=ae=null，直接ae.next会空指针异常

public class Partition {
        
        public ListNode partition(ListNode pHead, int x) {
        
            // write code here
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;
            ListNode cur = pHead;
            while (cur != null) {
        
                if (cur.val < x) {
        
                    if (bs == null) {
        
                        bs = be = cur;
                        cur = cur.next;
                    }else{
        
                        be.next = cur;
                    be = be.next;
                    cur = cur.next;
                    }
                    
                } else {
        
                    if (as == null) {
        
                        as = ae = cur;
                        cur = cur.next;
                    } else {
        
                        ae.next = cur;
                        ae = ae.next;
                        cur = cur.next;
                    }
    
                }
            }
            if (be == null) {
        
                return as;
            }
            be.next = as;
            if(ae!=null){
        
                ae.next = null;
            }
            return bs;
        }
    }

[ff7364d240d448059d3d56051c18cd23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f1fb85d39cc94c728fc329108797c468.png
[ecdb8fb7eadb4a039a5be2df2ac95ee3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/aee065a0699f4a0e90a45beab871ea80.png
[9235d7a01710452688fd3764533b527a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/92a2e10132924b929eaf8d54b02383da.png
[3fbbcff71c71420d8c42158c29fc750f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/be7b521eb755448f943b967e105e0429.png
[0919bdf31cef4690acda66c32e4a7bdf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/04891a81f1a74502943072e7fac97105.png