算法学习day04链表part02-24、19、0207、142

package SecondBrush.LinkedList.LL1;



/**
 * 24. 两两交换链表中的节点
 * */
public class SwapNodesInPairs_24 {

    public ListNode swapPairs(ListNode head){
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        ListNode cur = dummyhead;
        ListNode temp;
        ListNode firstnode;
        ListNode secondnode;
        while (cur.next != null && cur.next.next != null){
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;
            secondnode.next = firstnode;
            firstnode.next = temp;
            cur = temp;
        }
        return dummyhead.next;
    }

}

package SecondBrush.LinkedList.LL1;
/**
 * 19. 删除链表的倒数第 N 个结点
 * */
public class RemoveNthNodeFromEnd_19 {
    public ListNode remove(ListNode head,int n){
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        ListNode fastindex = dummyhead;
        ListNode slowindex = dummyhead;
        for (int i = 0; i < n; i++) {
            fastindex = fastindex.next;
        }
        while (fastindex != null){
            fastindex = fastindex.next;
            slowindex = slowindex.next;
        }
        slowindex.next = slowindex.next.next;
        return dummyhead.next;
    }

}

package SecondBrush.LinkedList.LL1;

/**
 * 面试题 02.07. 链表相交
 *
 * */

public class IntersectionTwoLinked_0207 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 交换这里没看明白
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

}

package SecondBrush.LinkedList.LL1;


/**
 * 142. 环形链表 II
 *  1.判断链表是否环：可以使用双指针，一个跑的块，一个跑的慢，如果是环，肯定可以相遇在环内
 *  2.如果有环，如何找到这个环的入口：这个牵扯到数学计算
 * */

public class LinkedListCycleII_142 {
    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 index1 = fast;
                ListNode index2 = head;
                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

}