lc24两两交换链表中的节点

思路

模拟大法，注意dummy是主线，cur只是dummy完成任务的分身

代码

/**
 * 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 dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null){
            ListNode left = cur.next;
            ListNode right = cur.next.next;
            ListNode nextNode = right.next;
            cur.next = right;
            right.next = left;
            left.next = nextNode;
            cur = left;
        }
        return dummy.next;
    }
}

lc19删除链表中倒数第n节点

思路

双指针法，快指针先走n+1，和慢指针同时移动，注意空指针被赋值

代码

/**
 * 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 dummy = new ListNode(-1, head);
        ListNode slow = dummy, fast = dummy;
        for (int i = 0; i <= n; i++){
            fast = fast.next;
        }
        while (fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        if (slow.next != null){
            slow.next = slow.next.next;
        }
        return dummy.next;
    }
}

lc160链表相交

思路

统计两链表长度，并假设A是较长的，不可以破坏原头节点。跳过A的gap节点同时移动，寻找相交节点。

代码

/**
 * 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, gap = 0;
        ListNode curA = headA, curB = headB;
        while (curA != null) {
            curA = curA.next;
            lenA++;
        }
        while (curB != null) {
            curB = curB.next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        if (lenA < lenB){
            gap = lenB - lenA;
            ListNode temp = curA;
            curA = curB;
            curB = temp;
            int temLen = lenA;
            lenA = lenB;
            lenB = temLen;
        }
        gap = lenA - lenB;
        while (gap-- > 0){
            curA = curA.next;
        }
        for (int i = 0; i < lenB; i++){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

lc142环形链表II

思路

双指针法，快慢指针同时出发；有环根据数学推理找到入口节点

代码

/**
 * 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) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                fast = head;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}