代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19. 删除链表的倒数第 N 个结点、160. 链表相交、142. 环形链表 II

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

leetcode
文档题解
视频题解

考察链表的基本操作,操作当前节点,获取上一个节点,保存下一个节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建虚拟头节点,因为可能会修改头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // 保存上一个节点的引用
        ListNode prev = dummyHead;
        ListNode curr = head;

        while (curr != null && curr.next != null) {
            // 保存下一对的起始节点的引用
            // 下次循环要从这个引用开始
            ListNode tmp = curr.next.next;
            // 反转,交换顺序也无妨
            prev.next = curr.next;
            curr.next.next = curr;
            // 把断开的节点再连上
            curr.next = tmp;
            // 前进
            prev = curr;
            curr = curr.next;
        }

        return dummyHead.next;
    }
}

看图:

由迭代法可知递归法:

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // 开始递归处理
        helper(head, dummyHead);

        // 返回链表反转后的头节点
        return dummyHead.next;
    }

    public void helper(ListNode curr, ListNode prev) {
        // 没有节点,或者只有一个节点,无需反转,不做处理
        if (curr == null || curr.next == null) return;

        // 保存下一对起始节点的引用
        ListNode tmp = curr.next.next;
        // 开始反转
        prev.next = curr.next;
        curr.next.next = curr;
        // 记得连接,否则就断了
        curr.next = tmp;

        // 递归处理下一对
        helper(curr.next, curr);
    }
}

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

leetcode
文档讲解
视频讲解

知识点:

  1. 单链表删除节点,需要知道前一个节点。
  2. 倒数第 n 个节点,就是正数第 size - n + 1 个节点。
  3. 从第 i 个节点遍历,到达第 j 个节点,需要前进 j - i 步。

第一种解法:可以从头开始遍历,第 size - n + 1 个节点就是要删除的节点(循环 size - n 次),但是首先得知道链表的长度。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // 计算长度
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            len++;
        }

        // 前进到第 size - n + 1 个节点,得循环 size - n 次
        n = len - n;
        curr = head;
        ListNode prev = dummyHead;
        while (n > 0) {
            prev = curr;
            curr = curr.next;
            n--;
        }

        if (curr != null) {
            prev.next = curr.next;
        }

        return dummyHead.next;
    }
}

第二种解法:我们可以先定义两个指针,一个指针从 head 开始,先前进 n 步,然后另一个节点也从 head 开始,然后两个节点同时前进,当第一个节点到达链表末尾的时候,第二个节点正好到达第 n 个节点,但是要删除第 n 个节点,所以要获取前一个节点,即第 n - 1 个节点,因此第二个节点得从虚拟头节点开始。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 因为要删除节点,所以用虚拟头节点统一操作
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        // prev 从 dummyHead 开始,表示要删除节点的前一个节点
        ListNode prev = dummyHead;
        // curr 从 head 开始遍历链表
        ListNode curr = head;

        // curr 前进 n 步
        while (curr != null && n > 0) {
            curr = curr.next;
            n--;
        }

        // prev 和 curr 同时前进,直到 curr 为 null
        while (curr != null) {
            prev = prev.next;
            curr = curr.next;
        }

        // 删除第 n 个节点
        prev.next = prev.next.next;

        return dummyHead.next;
    }
}

160. 链表相交

leetcode
文档讲解

链表相交即两个链表从某个节点开始,往后都相等。根据题目的图可以想到,将两个链表尾部对齐,让两个链表从同一长度开始遍历(让较长的链表前进几步),如果碰到某个节点相同,那么这就是交点,否则没有交点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode currA = headA;
        ListNode currB = headB;

        // 先计算长度
        while (currA != null) {
            currA = currA.next;
            lenA++;
        }

        while (currB != null) {
            currB = currB.next;
            lenB++;
        }

        currA = headA;
        currB = headB;

        // 长度长的,往前走几步
        if (lenA > lenB) {
            int x = lenA - lenB;
            while (x > 0) {
                currA = currA.next;
                x--;
            }
        } else {
            int x = lenB - lenA;
            while (x > 0) {
                currB = currB.next;
                x--;
            }
        }

        // 从同一长度开始遍历
        while (currA != null && currB != null && currA != currB) {
            currA = currA.next;
            currB = currB.next;
        }

        // 循环结束,如果 currA == currB,那么都指向交点,返回哪个都行
        // 如果有一个是 null,那说明不相交
        return currA;
    }
}

142. 环形链表 II

leetcode
文档讲解
视频讲解

Floyd 的环路查找算法:使用快慢指针,慢指针一次移动一格,快指针一次移动两格,如果没有环,则快指针率先到达 null,循环结束;如果有环,则快慢指针一定会相遇(?),且快指针走的距离是慢指针的两倍。当快慢指针相遇时,将慢指针重置到 head,快指针还在相遇点,然后二者同时前进,一次走一格,再次相遇时即为环的入口。

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

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

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

        // 有环,找入口点
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}

参考资料

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注