链表相关练习--2

目录

1、链表分割

2、找出两个链表的公共结点

3、判断链表是否有环

4、找到有环链表的入口点

---

1、链表分割

牛客：链表分割_牛客题霸_牛客网

思路：

1. 遍历链表，小于 x 的放到一起，大于等于x的放到一起，分成两段链表

2. 不改变原有顺序，需要使用尾插法

3. 最后把两段链表穿起来，返回第一段链表的首节点即可

4. 考虑特殊情况，所有节点都是 >= x 的，也就是说前半段链表是空，结点都在后半段，此时需再加一个第一个区间没有数据的语句

5. 注意，若第二个区间有数据，需要把第二个区间的最后一个结点的 next 置空，否则可能会出现死循环的错误

public ListNode partition(ListNode pHead, int x) { if(pHead == null) { return null; } ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; // cur 用于遍历链表 ListNode cur = pHead; while(cur != null) { if(cur.val < x) { if(bs == null) { //插入第一个节点 bs = cur; be = cur; }else { be.next = cur; be = be.next; } }else { if(as == null) { as = cur; ae = cur; }else { ae.next= cur; ae = ae.next; } } cur = cur.next; } //开始串起来 if(bs == null) { //第一个区间没有数据 return as; } //第一个区间有数据 be.next = as; if(as != null) { //第2个区间有数据 ae.next = null; } return bs; } 2、找出两个链表的公共结点

 oj：160. 相交链表 - 力扣（LeetCode）

思路：

1. 分别求两个链表的长度

2. 让长的 head 先走差值步

3. head1 和 head2 同时走

4. 相遇的阶段就是要找的结点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pl = headA; ListNode ps = headB; int len1 = 0; int len2 = 0; //1、求长度 while(pl != null) { len1++; pl = pl.next; } while(ps != null) { len2++; ps = ps.next; } pl = headA; ps = headB; int len = len1 - len2; if(len < 0) { //修正一下 pl和ps的指向 pl = headB; ps = headA; len = len2-len1; } // 此时pl一定指向最长的链表，ps一定指向最短的链表；len一定是一个正数 //2、走差值步 while(len != 0) { pl = pl.next; len--; } //3、同时走 while(pl != ps) { pl = pl.next; ps = ps.next; } // 两个链表没有交点 if(ps == null) { return null; } // 4、返回相遇结点 return pl; } 3、判断链表是否有环

oj：141. 环形链表 - 力扣（LeetCode）

思路：

1. 追击问题，在有环的情况下，使用快慢指针，fast 只要每次比 slow 多走一步，最终一定会相遇；fast 走2步，slow 走1步是最快的情况，因为它们最多追击一个环的长度，一定不会出现slow在环里走很多圈的情况。

2. 如果没有环，走得快的一定先为空，即 fast == null || fast.next == null

public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return true; } } return false; } public boolean hasCycle2(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { break; } } if(fast == null || fast.next == null) { return false; } return true; } 4、找到有环链表的入口点

oj：142. 环形链表 II - 力扣（LeetCode）

推导：

设起始点到入口点的距离为X，相遇点到入口点的距离为Y，环的长度为C

快指针走的路程：X+NC+(C-Y)

慢指针走的路程：X+(C-Y)

  2*(X+(C-Y))=X+NC+(C-Y)   X+C-Y=NC   X=NC-C+Y   X=(N-1)*C+Y   N=1时，X=Y

结论：无论 Y 在环中转了多少圈，让 slow 从头走，fast 从相遇点走，一步一步走，相遇的地方就是入口点

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