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

  1. 两两交换链表中的节点 题目链接
    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

方法:

  • 递归
    返回值:交换完成的子链表
    调用单元:设需要交换的两个点为 head 和 next,head 连接后面交换完成的子链表,next 连接 head,完成交换
    终止条件:head 为空指针或者 next 为空指针,也就是当前无节点或者只有一个节点,无法进行交换
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归终止    条件:head 为空指针或者 next 为空指针,也就是当前无节点或者只有一个节点,无法进行交换
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        // head 连接后面交换完成的子链表
        head.next = swapPairs(next.next);
        // next 连接 head,完成交换
        next.next = head;
        // 新头节点
        return next;
    }
}
  • 非递归写法
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        while(pre.next != null && pre.next.next != null){
            // 俩节点互换前先临时保存后面子链的头节点
            ListNode tempNode = head.next.next;
            // 第一步 虚拟节点指向2节点(第一个例子)
            pre.next = head.next;
            // 第二步 2节点指向1节点
            head.next.next = head;
            // 第三步 1节点指向临时保存的3节点
            head.next = tempNode;
            // 更新pre和head,继续循环
            pre = head;
            head = tempNode;
        }
        return dummyNode.next;
    }
}

19.删除链表的倒数第N个节点 题目链接
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

思路:

  • 最容易想到的思路是,先计算链表的长度L,然后第 L-n+1 个节点就是要删除的节点;遍历到L-n的位置,就可以删除第L-n+1个节点了
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = getLength(head);
        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        // 找到第len-n+1个节点的前驱节点
        for (int i = 0; i < len - n ; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummyNode.next;
    }
    private int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode cur = head;
        int result = 0;
        while(cur != null) {
            result++;
            cur = cur.next;
        }
        return result;
    }
}
  • 前后指针确定删除节点位置
    创建指向head的虚拟头结点dummyNode,前指针指向dummyNode,后指针指向前指针移动n+1步后的位置,然后俩指针同时每次步进1,直到后指针指向null,此时前指针指向了要删除的节点的前驱节点
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1, head);
        ListNode frontNode = dummyNode;
        ListNode backNode = dummyNode;
        // 后指针backNode向后移动n+1步
        for (int i = 0; i <= n; i++) {
            backNode = backNode.next;
        }
        // 前后指针同时移动,直到backNode指向null,此时front指针指向了要删除的节点的前驱节点
        while (backNode != null) {
            frontNode = frontNode.next;
            backNode = backNode.next;
        }
        // 开始删除节点
        frontNode.next = frontNode.next.next;
        return dummyNode.next;
    }
}

160.链表相交
题目链接 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
思路:

  • 最容易想到的思路是,利用哈希集合的contains方法:把一个链表的节点全部存入hashSet中,然后遍历另一个链表,如果某节点存在于hashSet中,说明该节点就是相交节点
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> setA = new HashSet<>();
        ListNode cur = headA;
        while (cur != null) {
            setA.add(cur);
            cur = cur.next;
        }
        cur =  headB;
        while (cur != null) {
            if (setA.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}

142.环形链表II
题目链接
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路:推导过程较复杂,先记着思路
第一步:快慢指针指针指向头节点,慢指针步进1,快指针步进2,如果相遇则链表有环,否则不然;
第二部:有环后,一个指针指向头节点,一个指针指向头节点,一个指针指向第一步的相遇点,然后俩指针同时步进1,新的相遇点即为入环点;

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // fast指向无环链表最后一个节点或者fast指向null结束
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 相遇有环
            if (slow == fast) {
                ListNode fisrtNode = head;
                ListNode meetingNode = slow;
                while (fisrtNode != meetingNode) {
                    fisrtNode = fisrtNode.next;
                    meetingNode = meetingNode.next;
                }
                return meetingNode;
            }
        }
        return null;
    }
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式