链表 OJ(一)

发布于:2024-07-11 ⋅ 阅读:(25) ⋅ 点赞:(0)

移除链表元素

题目连接:
https://leetcode.cn/problems/remove-linked-list-elements/description/

在这里插入图片描述

使用双指针法,开始时,一个指针指向头节点,另一个指针指向头节点的下一个结点,然后开始遍历链表删除结点。

这里要注意如果是空链表的话,使用双指针第二个指针会发生空指针异常,所以要判断一下

最后程序运行到最后,我们还差头节点没有判断,最后加上即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return head;
        }

        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }

        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
}

反转链表

题目连接:
https://leetcode.cn/problems/reverse-linked-list/description/

在这里插入图片描述


我们还是使用双指针,不过这次有一个指针就是头指针,因为反转链表之后的头指针会发生改变,那还不如直接让头指针一起移动,先将另一个指针指向头指针的下一个结点,然后开始遍历链表,把每一个结点的指针指向的对象变为前面的对象。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return head;
        }
        
        ListNode cur = head.next;
        head.next = null;

        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = head;
            head = cur;
            cur = tmp;
        }
        
        return head;
    }
}

链表的中间结点

题目链接:
https://leetcode.cn/problems/middle-of-the-linked-list/description/

在这里插入图片描述


使用快慢指针,快指针每次走两步,慢指针每次走一步,最后慢指针所指向的结点就是 中间结点

原理:fast = 2slow = 总路程

这里要注意循环的结束条件:
在这里插入图片描述当fast== null 并且 fast.next == null时,才能进入循环,并且 fast==null,要放在前面,因为只用fast不是null时才能进行 fast.next 的判断

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

返回倒数第 k 个节点

题目链接:
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

在这里插入图片描述


还是使用快慢指针,先让快指针走 k-1 步,然后慢指针和快指针一起走,每次走一步,最后快指针走到最后一个结点时,慢指针所指向的节点就是倒数第 k 个节点。

原理就是让slow和fast的差值j就是k

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        for(int i=0; i<k-1; i++) {
            fast = fast.next;
        }

        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow.val;
    }
}

合并两个有序的链表

题目链接:
https://leetcode.cn/problems/merge-two-sorted-lists/description/
在这里插入图片描述


创建一个新的头节点,list1和list2开始遍历各自的链表,然后比较,插入到新链表中,最后再看一下哪些链表没有遍历完,然后把没有遍历完的链表直接插入即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return newHead.next;
    }
}

分割链表

题目链接:
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

在这里插入图片描述


我们可以将单链表拆成两个链表,一个链表存储小于x 的结点,另一个链表存储大于等于x 的结点,然后将两个链表合并

这里建议使用带头链表,也就是我们常说的带哨兵位的链表,这个链表最大的好处就是可以避免头插的复杂情况,既然使用了哨兵位,就要知道最后哨兵位是要被丢弃的。

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode headA = new ListNode(-1);
        ListNode aLast = headA;
        ListNode headB =  new ListNode(-1);
        ListNode bLast = headB;

        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                aLast.next = cur;
                aLast = aLast.next;
            } else {
                bLast.next = cur;
                bLast = bLast.next;
            }
            cur = cur.next;
        }

        aLast.next = headB.next;
        bLast.next = null;
        return headA.next;
    }
}

链表的回文结构

题目链接:
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
在这里插入图片描述


解题思路:
我们可以使用快慢指针来遍历链表找到中间结点,然后就可以把后半部分的链表进行反转,之后从这个链表头尾结点开始向中间遍历。

易错点:
1.链表的结点个数有奇数和偶数两种类型,我们需要分别讨论
2.区分奇数个结点还是偶数个结点可以从一开始找完中间结点的时候,从fast入手,因为找中间结点的循环结束就是fast最后指向尾节点还是null。
3.要一定要保存好fast的信息,因为后面在反转链表的时候fast其实已经发生了改变。

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        //如果是空链表返回true
        if(A == null) {
            return true;
        }

        ListNode slow = A;
        ListNode fast = A;

        //找到中间结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //保存fast的结点信息,避免后面反转链表丢失信息
        boolean isOdd = true;//是否是奇数个结点
        if(fast == null) {
            isOdd = false;
        }

        //反转后半部分的链表
        ListNode prev = slow;
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curN;
        }

        //前后遍历链表
        ListNode pA = A;
        ListNode last = prev;

        //偶数个结点
        if(!isOdd) {
            while(pA.next != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
            if(pA.val != last.val) {
                return false;
            }
        }
        if (isOdd) { //奇数个结点
            while(pA != last) {
                if(pA.val != last.val) {
                    return false;
                }
                pA = pA.next;
                last = last.next;
            }
        }

        return true;
    }
}

相交链表

题目链接:
https://leetcode.cn/problems/intersection-of-two-linked-lists/

在这里插入图片描述


由于是相交链表,在公共结点之前两个链表可能有一个差值,如果我们能找到这个差值,让长的链表先走差值不属,然后两个链表一起遍历,直到相遇到公共结点。

这个差值就是两个链表的长度的差。

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 k = 0;
        ListNode pl = null;
        ListNode ps = null;
        if(lenA > lenB) {
            k = lenA - lenB;
            pl = headA;
            ps = headB;
        } else {
            k = lenB - lenA;
            pl = headB;
            ps = headA;
        }

        while(k != 0) {
            pl = pl.next;
            k--;
        }

        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        return pl;
    }
}

环形链表

题目链接:
https://leetcode.cn/problems/linked-list-cycle/

在这里插入图片描述


这里使用快慢指针,快指针一次走两步,慢指针一次走一步,当快指针运动到fast == null 或者 fast .next == null 这个条件时,说明链表不存在环,如果有链表存在环,那么快指针就会先进入到环中一直做圆周运动,一定会存在某一个时刻快慢指针会相遇,这时候返回true即可。

public 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(fast == slow) {
                return true;
            }
        } 

        return false;
    }
}

为什么快指针每次走两步,慢指针走一步可以?

快指针会率先进入环中,然后慢指针后晚一点进入环中,由于两个指针的速度是每次差一步,也就是说两个指针每运动一次,二者之间的距离就会缩短1步,最后两个指针一定会相遇。

快指针一次走3步,走4步,…n步行吗?
快指针如果每次走三步,假设两个指针的位置如下:
在这里插入图片描述
那二者永远都不会相遇

其他情况由读者自行探讨~~

环形链表Ⅱ (找入口点)

题目链接:
https://leetcode.cn/problems/linked-list-cycle-ii/description/

在这里插入图片描述


我们还是使用快慢指针来做。

假设起点与入口点的距离为 x ,环的周长为 C ,慢指针与快指针相遇点离起点的距离为L
在这里插入图片描述
慢指针所走的路程为 x + L
快指针所走的路程为 x + L + nC (n为正整数,n = 1,2,3,4…)

这里解释一下两者的路程计算问题:
在慢指针还没有进入口点的时候,就已经至少路过一次相遇点,所以当慢指针刚刚进入环中的时候,快指针最少已经走了一圈,最多走了 n 圈。
因为慢指针刚进入环中的时候,快指针和它最多相差一个圈的距离,并且快指针的速度比慢指针的速度要快,所以慢指针是不可能走完一圈的(假设慢指针走完一圈,那快指针一定走完一圈再多一点,所以慢指针在完成一圈之前一定会被追上),所以慢指针所走的路程为 x + L,快指针所走的路程为 x + L + nC (n为正整数,n = 1,2,3,4…)中的 nC 是遇到慢指针之前就已经完成好的

当快慢指针在环中相遇时,由于快指针的速度是慢指针的速度的两倍,所以慢指针的路程是快指针的一半,即 2 * (x + L) = x + L + nC,化简整理得 x + L = nC 即 x = nC - L

推导结论:
让一个指针从头开始遍历,另一个指针从相遇点开始遍历,两个指针每次走一步,一定会在入口点相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }

        //没有环
        if(fast == null || fast.next == null) {
            return null;
        }

        ListNode meet = fast;
        ListNode str = head;

        while(meet != str) {
            meet = meet.next;
            str = str.next;
        }
        
        return str;
    }
}