Collection与数据结构链表与LinkedList(三):链表精选OJ例题(下)

1. 分割链表

OJ链接

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;//空链表的情况
        }
        ListNode cur = head;
        ListNode formerhead = null;
        ListNode formerend = null;
        ListNode latterhead = null;
        ListNode latterend = null;//定义链表分区
        while (cur != null){//遍历链表
            if(cur.val < x){
                if(formerhead == null){
                    formerhead = cur;
                    formerend = cur;//第一次遍历头和尾都为null
                    //formerend = formerend.next;错误,不可以使得formerend向下走,否者为null,会空指针异常
                }else{
                    formerend.next = cur;
                    formerend = formerend.next;//formerend全程不可以为空
                }
            }
            if(cur.val >= x){
                if(latterhead == null){
                    latterhead = cur;
                    latterend = cur;
                }else{
                    latterend.next = cur;
                    latterend = latterend.next;
                }
            }
            cur = cur.next;
        }
        if(formerhead == null){//链表前段位空时的情况,formerend为空,下面会报异常
            return latterhead;
        }
        if(latterhead != null){//当链表后段不为空时,(为空不走这一步,否则空指针异常),链表的最后需要手动置为null
            latterend.next = null;
        }
        formerend.next = latterhead;//之所以上面要求formerend全程不为空,是因为这一步会报异常,null
        return formerhead;
    }
}

整体思路:
创建一个新的链表,把这个新的链表用x分段,遍历原链表,根据条件把结点放入新链表,之后把前面一段链表和后面一段链表连接起来.

[注意事项]

1. 要始终保持fe(formerend)不为空,否者在最后连接的时候就要报空指针异常
2. 考虑几种特殊情况

• 链表为空,返回null
• 前半段链表为空,在最后连接的时候会报空指针异常,所以在最后的时候返回lb即可.
• 当后半段链表不为空的时候,最后一个结点的next有可能不为null,所以要对最后手动置空,否者会越界.

动态演示

2. 回文链表

OJ链接

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null){//空链表情况下
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;//找到中间结点
        }
        cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;//在循环体中定义ListNode,防止空指针异常
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }//翻转后半段链表
        cur = head;
        while(cur != slow){//奇数判断回文
            if(cur.val != slow.val){
                return false;
            }
            if(cur.next == slow){//偶数判断回文
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }
}

整体思路:
先使用快慢指针找到中间节点,之后将后半段链表使用头插法翻转.之后把head和slow向中间遍历,相遇就是回文.

[注意事项]

1. 注意区分奇偶数,奇数整体思路没问题,但是偶数永远不会相遇,此时就需要引入if(cur.next == slow)判断偶数情况.

动态演示

3. 相交链表

OJ链接

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode cur = headA;
        while(cur != null){
            lenA++;
            cur = cur.next;
        }
        cur = headB;
        while(cur != null){
            lenB++;
            cur = cur.next;
        }//计算两个链表的长度
        int len = lenA-lenB;//计算长度之差,但是有可能为负数
        ListNode longList = headA;
        ListNode shortList = headB;//定义长链表和短链表,如果len为正,则longList为A,另一个为B
        if(len < 0){//负数则相反
            longList = headB;
            shortList = headA;
            len = lenB-lenA;//把len变为正数
        }
        while(len != 0){
            longList = longList.next;
            len--;//先让长链表走差值步
        }
        while(longList != shortList){
            longList = longList.next;
            shortList = shortList.next;//之后一起走,直到相交
        }
        if(longList == null || shortList == null){
            return null;//没有交点的情况
        }
        return longList;//返回交点
    }
}

整体思路
先让长链表走短链表与长链表的差值步,之后一起走,相遇之后就有交点.

[注意事项]

1. 不确定哪个链表长,哪个链表短,所以长度的差值可能为负数.我们定义长链表和短链表来解决这个问题,利用长度的差值来判断长短.
2. 有一个非常隐形的问题,链表可能不想交,所以我们要用if(longList == null || shortList == null)来限制.虽然没有这句话也可以跑过,是因为最后longList和shortList都走到了null,返回longList正好也是null.所以这个问题非常隐性.

动态演示

4. 环形链表

OJ链接

ublic class Solution {
    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(slow == fast){//在走的过程中再判断什么时候相等,返回即可
                return true;
            }
        }
        return false;
    }
}

整体思路
定义一个快指针,一个慢指针,快指针一次走两步,慢指针一次走一步,最终进入环的时候必定会相遇.相遇一定就有环.

[注意事项]

1. 首先判断的是链表有没有环,这是循环的条件.
2. 在循环体内部再判断会不会相遇.

动态演示

5. 寻找环形链表的环入口

OJ链接

public class Solution {
    public ListNode 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){//相遇的情况
                while(head != slow){
                    head = head.next;
                    slow = slow.next;//向环的入口靠近
                }
                return slow;//相遇的位置即为入口
            }
        }
        return null;
    }
}

整体思路
先找到相遇的点,之后根据数学推导可知,链表头到入口的距离与相遇点到入口的距离相等,让head和slow同时向入口处走,相遇的地方就是要返回的点.

[数学推导]

动态演示