(Java数据结构)链表题

环形链表

判断链表中是否有环

leetcode
141. 环形链表

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

如果每次快指针走2步，慢指针走1步，最坏的情况下，慢指针刚入环时，快指针比慢指针多走一个环的路程，因为每次快指针比慢指针多走1步，所以在慢指针还没走到一圈时，快指针一定可以追上慢指针

如果环中只有两个节点这种情况，如果快指针每次走3步，慢指针每次走1步，那么快慢指针永远不能相遇

所以将快指针设置为每次走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

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

假设快指针比慢指针多走N圈时相遇，即慢指针走了X+C-Y，快指针走了X+C-Y+NC，因为快指针速度是慢指针的2倍，所以相同时间内，快指针走的距离是慢指针的2倍，即X+C-Y+NC=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的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

举例：以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;
    }
}