代码随想录算法训练营第4天 | 24. 两两交换链表中的节点 , 19.删除链表的倒数第N个节点 , 面试题 02.07. 链表相交 , 142.环形链表II

发布时间:2024年01月14日

链表知识基础

文章链接:https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#

24. 两两交换链表中的节点

题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/
使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。

思路:使用虚拟头结点

设置一个虚拟头结点,这样原链表的所有节点就都可以按照统一的方式进行移除了。
然后注意一下,就是while里面,判断的条件有两个,pre.next != null && pre.next.next != null,才可以交换,也就是后面一个,和后面两个结点都不是null的情况,才可以。同时写的顺序也不能反,否则会报null.next的错误

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        while(pre.next != null && pre.next.next != null){
            // ListNode tmp = pre.next.next;
            // pre.next.next = tmp.next;
            // tmp.next = pre.next;
            // pre.next = tmp;
            // pre = pre.next.next;
            ListNode firstNode = pre.next;
            ListNode secondNode = pre.next.next;
            firstNode.next = secondNode.next;
            secondNode.next = pre.next;
            pre.next = secondNode;
            pre = pre.next.next;
        }
        return dummyNode.next;
    }
}

时间复杂度 O(n)

19. 删除链表的倒数第 N 个结点

题目连接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。尝试用一遍扫描实现。

解法:快慢指针

让快指针先移动n步,然后这样再同时移动。
此时快指针移动了size-n步,慢指针也是size-n步,此时慢指针离最后距离也是size-(size-n)=n,也就是题意。
写过一次,有思路就很快了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // 快慢双指针
        ListNode slow=dummyNode,fast=dummyNode;
        // 快指针先移动n步
        for(int i=0;i<n;i++)
        {
            fast = fast.next;
        }
        // 然后这个时候,快指针和慢指针,再同时移动。直到快指针移动到最后
        while(fast.next!=null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        // 此时的slow指针指向的是要删除的结点的前一个
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

时间复杂度O(n)

面试题 02.07. 链表相交

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

解法:求两个链表交点节点的指针

特别注意!!! 交点不是数值相等,而是指针相等。不用比较val,只要比较两个指针是否相等,即可
还有个地方,两个链表的末端一定要先对齐,要不然不满足题意。也就是说,两个链表的指针起始位置是不一样的。一个是在开始处,一个不是。
在这里插入图片描述

/**
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先求两个链表的长度
        int lenA = 0, lenB = 0;
        ListNode curA = headA,curB = headB;
        while(curA!= null)
        {
            curA = curA.next;
            ++lenA;
        }
        while(curB!=null)
        {
            curB = curB.next;
            ++lenB;
        }
        curA = headA;
        curB = headB;
        // 把A确定为更长的
        if(lenA<lenB){
            // 交换结点
            ListNode tmp = curB;
            curB = curA;
            curA = tmp;
            int tmpLen = lenB;
            lenB = lenA;
            lenA = tmpLen;
        }
        // 对齐末端
        int gap = lenA-lenB;
        while(gap-- >0)
        {
            curA = curA.next;
        }
        // 然后这个时候再比较指针是否相同,不是比较val是否相同
        while(lenB-- >0)
        {
            if(curA==curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

时间复杂度:O(n)

142.环形链表II

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

解法1:快慢指针法

主要考察两知识点:
(1)判断链表是否环
(2)如果有环,如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。相对于slow来说,fast是一个节点一个节点的靠近slow的,所以fast一定可以和slow重合。

如果有环,如何找到这个环的入口

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:
在这里插入图片描述
slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针, (y+z)为 一圈内节点的个数A。
(slow指针肯定是走了一圈不到的,因为他俩的速度差在一圈内是完全追的上的)

因为fast指针是一步走两个节点,slow指针一步走一个节点, 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2:

(x + y) * 2 = x + y + n (y + z)

两边消掉一个(x+y): x + y = n (y + z)

因为要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。

所以要求x ,将x单独放在左面:x = n (y + z) - y ,

再从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢?

先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。

当 n为1的时候,公式就化解为 x = z,

这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。

让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 方法2:快慢指针
        ListNode slowIndex = head,fastIndex = head;
        while(fastIndex!=null && fastIndex.next != null){
            // 快指针一次移动两格,慢指针一次移动一格
            fastIndex = fastIndex.next.next;
            slowIndex = slowIndex.next;
            // 有环的情况
            if(slowIndex == fastIndex){
                // 相交的点
                ListNode joint = slowIndex;
                ListNode startNode = head;
                // 需要数学证明!
                // 从头结点出发一个指针,从相遇节点也出发一个指针,这两个指针每次只走一个节点, 
                // 那么当这两个指针相遇的时候就是 环形入口的节点。
                while(startNode!=joint){
                    joint = joint.next;
                    startNode = startNode.next;
                }
                return joint;
            }
        }
        return null;

    }
}

时间复杂度:O(n)
空间复杂度:O(1)

解法2:哈希法

一种非常直观的解法,我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希表可以很方便地实现。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 方法1:哈希表的方式
        ListNode cur = head;
        HashSet<ListNode>nodes = new HashSet<ListNode>();
        while(cur!=null){
            if(nodes.contains(cur))
                return cur;
            else
                nodes.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

时间复杂度:O(n)
空间复杂度:O(n),n为链表中节点的数目

文章来源:https://blog.csdn.net/Captain_Aaron/article/details/135589271
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。