您现在的位置是：首页 >其他 >代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 ，19.删除链表的倒数第N个节点 ，07. 链表相交，142.环形链表II网站首页其他

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

题目链接：力扣

思路：这道题对我来说比较难，我对于翻转链表都是处于记忆化的理解程度，所以两两交换链表节点就比较困难了。

对这道题而言，还是需要用到dummy节点简化问题的边界处理情况，在翻转的过程中，先保存原始节点的next及next.next节点，然后按照题目的意思重新定向指针。

代码：

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

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode curNode = dummy;
        while (curNode.next != null && curNode.next.next != null) {
            ListNode tmpA = curNode.next;
            ListNode tmpB = curNode.next.next.next;

            curNode.next = curNode.next.next;
            curNode.next.next = tmpA;
            tmpA.next = tmpB;
            curNode = curNode.next.next;
        }

        return dummy.next;
    }
}

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

题目链接：力扣

思路：这道题有三种思路：

（1）将链表两次翻转，其中第一次翻转是为了将倒数第N个节点转化为正数第N个节点来解决问题（我本题使用的方法）；

（2）将链接遍历两次，第一次是为了得到链表的长度，方便定位倒数第N个节点，其实是正数第M个节点，其实也是转换问题思考的角度；

（3）利用快慢指针，其中快指针多跑N个节点，快慢指针之间的距离是N + 1个节点，这样当快指针遍历到链表末尾时，慢指针正好处于需要删除的节点之前，然后进行删除操作。

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n == 1 && head.next == null) {
            return null;
        }

        ListNode reverseList = reverse(head);
        ListNode tmpNode = new ListNode();
        tmpNode.next = reverseList;
        ListNode dummy = tmpNode;
        while (n - 1 > 0) {
            dummy = dummy.next;
            n--;
        }
        dummy.next = dummy.next.next;

        return reverse(tmpNode.next);
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        
        return pre;
    }
}

LeetCode 07. 链表相交

题目链接：力扣

思路：有两种解法：

（1）遍历两个链表得到各自链表长度，将长链表设置快指针多跑长链表与短链表长度之差个节点，也就是分别将两个链表上的遍历指针都对齐在同一个长度节点上。然后判断两个节点是否相等。

（2）直接遍历两个链表，将链表节点存储在List<ListNode>列表中，判断是否出现过。（我本题的解法）

代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        List<ListNode> list = new ArrayList<>();
        
        while (headA != null) {
            list.add(headA);
            headA = headA.next;
        }       
        
        while (headB != null) {
            if (list.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

LeetCode 142.环形链表II

题目链接：力扣

思路：首先利用快慢指针判断链表是否存在环，快指针比慢指针多跑一个节点；然后从相遇节点和链表头节点同时出发，再次相遇的节点就是环的入口。

代码：

public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode tmpA = fast;
                ListNode tmpB = head;
                while (tmpA != tmpB) {
                    tmpA = tmpA.next;
                    tmpB = tmpB.next;
                }
                return tmpA;
            }
        }
        return null;
    }