[代码随想录] 第四天

19.删除链表的倒数第N个节点https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路：使用前后指针，当删除倒数第N个节点时，快慢指针之间应该间隔N个元素，当快指针到达链尾时，慢指针next指向所要删除节点。
时间复杂度：O(N)

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

------------------------分割线-------------------------
24. 两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/495209174/
思路:①自行创建头节点②循环判断条件应为p.next!=null && p.next.next!=null，这样奇数偶数都可以完成节点交换。

/**
 * 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) {
        if (head == null) {
            return null;
        }
        ListNode fakeHead = new ListNode();
        fakeHead.next = head;
        ListNode begin = fakeHead;
        ListNode p = fakeHead;
        ListNode q;
        while (p.next != null && p.next.next != null) {
            q = p.next.next;
            p.next.next=q.next;
            q.next = p.next;
            p.next = q;
            p=p.next.next;
        }
        
        return fakeHead.next;
    }
}

------------------------分割线-------------------------
160.链表相交https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
思路：先求出两链表长度，两链表如有相交节点，一定位于短链表部分，因此长链表较长部分不做研究，从短链表头节点相应位置开始循环判断节点是否相同。

/**
 * 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 length_a = 0;
        int length_b = 0;
        ListNode p = headA;
        while (p != null) {
            length_a++;
            p = p.next;
        }
        p = headB;
        while (p != null) {
            length_b++;
            p = p.next;
        }
        p = headA;
        ListNode q = headB;
        int subValue = length_a - length_b;
         if (subValue >= 0) {
            p = headA;
            int i = 0;
            while (i < subValue) {
                i++;
                p = p.next;
            }

        } else {
            subValue = -subValue;
            int i = 0;
            while (i < subValue) {
                i++;
                q = q.next;
            }
        }
        while (p != null) {
            if (p == q) {
                return p;
            }
            p = p.next;
            q = q.next;
        }
        return null;

    }
}

-----------------------分割线-------------------------
142.环形链表IIhttps://leetcode.cn/problems/linked-list-cycle-ii/description/
思路：

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