随想录刷题笔记 —链表篇2 24两两交换链表节点 19删除倒数第N个节点 02 07链表相交 142环形链表II

24两两交换链表节点

两两交换相邻的节点

首先创建了哨兵结点。

其次创建3个指针，分别指向pre node1 node2， 交换node1和node2 

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode frehead = new ListNode(-1, head);
        ListNode prenode1 = frehead;
        while (prenode1.next!=null && prenode1.next.next!=null){
            ListNode node1 = prenode1.next;
            ListNode node2 = node1.next;
            prenode1.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            prenode1 = node1;
        }
        return frehead.next;
    }
}

19删除倒数第N个节点

删除链表的倒数第 n 个结点

首先创建了哨兵结点。

其次创建快慢指针，指针之间相距n，即快指针先向后移动n次，再与慢指针同时移动，直到快指针运行到链表尾。此时慢指针指向倒数第 n 个结点的前结点，删除倒数第 n 个结点轻而易举。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode frehead = new ListNode(-1, head);
        ListNode slow = frehead;
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return frehead.next;
    }
}

02 07链表相交

返回两个单链表相交的起始节点

相交的部分长度一定相同，因此长的链表的需要向短的链表统一

比较长度后建立新的起始点指针，同时向后查找

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null){
            return null;
        }
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while (nodeA.next!=null&&nodeB.next!=null){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        ListNode newheadA = headA;
        ListNode newheadB = headB;
        if (nodeA.next==null){
            while (nodeB.next !=null){
                newheadB = newheadB.next;
                nodeB = nodeB.next;
            }
        }else {
            while (nodeA.next !=null){
                newheadA = newheadA.next;
                nodeA = nodeA.next;
            }
        }
        if (nodeA!=nodeB){
            return null;
        }

        while (newheadA !=null){
            if (newheadA==newheadB){
                return newheadA;
            }
            newheadB = newheadB.next;
            newheadA = newheadA.next;
        }
        return null;
    }
}

142环形链表II

返回链表开始入环的第一个节点

使用O(n)存储：使用map存储结点，检验是否存在重复。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Map<ListNode, Integer> mapList = new HashMap<>();
        while (head!=null){
            if (mapList.containsKey(head)){
                return head;
            }else {
                mapList.put(head, 1);
            }
            head = head.next;
        }
        return null;
    }
}

使用O(1)存储：建立快慢指针，如果存在慢指针走一步，快指针走两步，直到相遇。

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){
                ListNode node1 = head;
                ListNode node2 = fast;
                while(node1 != node2){
                    node1 = node1.next;
                    node2 = node2.next;
                }
                return node1;
            }
        }
        return null;
    }
}

收获

快慢指针可以用于环操作