链表

LeetCode 24

看到题目的第一想法
就是采用2->1->4->3这种方法去转换，但是不知道循环的条件应该怎么判断，所以在进行操作的时候出现问题。

class Solution {
    
    public ListNode swapPairs(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode cur = head; //对于当前节点的指向也不清楚，所以就会乱写
        while(cur!=null && cur.next!=null){ //循环条件判断错误
            ListNode temp = cur.next;
            ListNode temp1 = cur.next.next;
            dummyHead.next = cur.next;
            cur.next = cur;
            cur=temp1;
        }
        return dummyHead.next;
    }
}

看完题解后的想法
首先要明确，cur指向dummy才能指向后面两个节点，每次操作两个节点进行交换，cur应该在要操作的两个节点前

dummy->1->2->3->4->5->null
|
cur

其次，有两种情况，一个是奇数个节点，那么循环结束的条件就是cur.next.next=null,因为后面的节点没有可交换的节点了

dummy->2->1->4->3->5->null
                |
                cur

如果是偶数节点，那么就是cur.next=null结束

dummy->2->1->4->3->null
                |
                cur

所以确定了循环的条件之后就可以进行操作了

class Solution {
    
    public ListNode swapPairs(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next!=null && cur.next.next!=null){
            ListNode temp = cur.next;
            ListNode temp1 = cur.next.next.next;
            cur.next=cur.next.next;
            cur.next.next = temp;
            cur.next.next.next = temp1;
            cur=cur.next.next;
        }
        return dummyHead.next;
    }
}

遇到的困难
循环条件不明确，开始时候的cur的指向不明确，是指向head还是指向dummyhead不清楚，这个要清楚交换的逻辑。

LeetCode 19

看到题目的第一想法
就是先翻转链表然后正向删除第n个节点，之后再翻转链表

class Solution {
    public ListNode reverseNode(ListNode cur){
        ListNode pre = null;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
    public ListNode deleteNode(ListNode node, int n){
        ListNode dummyHead=new ListNode();
        dummyHead.next=node;
        ListNode cur = dummyHead; //删除节点从dummyhead开始，不然会删除下一个，这个画图可以看出
        for(int i=1;i<n;i++){
            cur=cur.next;
        }
        cur.next=cur.next.next;
        return dummyHead.next;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return head;
        }
        ListNode node = reverseNode(head);
        ListNode node1 = deleteNode(node,n);
        ListNode node2 = reverseNode(node1);
        return node2;
    }
}

看完题解后的想法
这里的解题的思路很妙，首先因为是删除操作当然需要一个dummyhead，然后我们定义两个节点slow，fast指向dummyHead，然后fast向前走n+1步，然后slow和fast在同时走，当fast走到null，slow走到了要删除的元素的前一个。

class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead=new ListNode();
        dummyHead.next=head;
        ListNode fast=dummyHead;
        ListNode slow=dummyHead;
        n++;
        while(fast!=null && n>0){
            fast=fast.next;
            n--;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return dummyHead.next;
    }
}

遇到的困难
不太能想到定义两个指针，然后让一个节点先走n+1步，这个思路比较新。

链表相交02.07

看到题目的第一想法
看到题目的第一想法就是要两个链表然后从头到尾开始遍历，如果遇到相等的节点然后就返回，否则返回null。这里面有些很细节的东西要考虑，比如，比较的时候怎么比较。
看完题解后的想法
做一个差值比较，就是长的链表-短链表，然后让长链表移动差值，之后再开始比较，也就是比较的时候并不是一开始就两个链表从头比较。注意计算完两个链表的长度之后要重新将curA,curB赋值，否则后面会出错。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA=headA;
        ListNode curB=headB;
        int sizeA=0,sizeB=0;
        int result=0;
        while(curA!=null){
            curA=curA.next;
            sizeA++;
        }
        while(curB!=null){
            curB=curB.next;
            sizeB++;
        }
        curA=headA; //重新赋值
        curB=headB;
        ListNode temp;
        if(sizeA<sizeB){
            result=sizeB-sizeA;
            temp=curA;
            curA=curB;
            curB=temp;
        }else{
            result=sizeA-sizeB;
        }
        while(result>0){
            curA=curA.next;
            result--;
        }
        while(curA!=null && curB!=null){
            if(curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}

遇到的困难
没有想到链表是先让长链表移动差值个单位，然后再和短链表一起移动进行比较。

LeetCode 142

看到题目的第一想法
如何确定循环链表，不清楚
看完题解后的想法
通过两个指针，一个快指针一个慢指针，快指针一次走两个节点，慢指针一次走一个节点，那么一定会在循环中相遇，并且快指针一定会追上慢指针，因为快指针相对慢指针的速度，相对速度是一个节点所以一定会追上。所以这里不能考虑快指针一次走三个四个节点的情况。

是一个数学问题，就是其实我们实际计算的是，fast和slow相遇的节点出发，然后另一个从头结点出发，直到两个节点相等，那么这个节点就是第一个入口节点。
在这里插入图片描述

slow : x+y
fast: x+y+n(y+z)

fast=2*slow
2*(x+y)=x+y+n(y+z)
x=(n-1)(y+z)+z
可以看出这里x和z的关系，也就是从x,z出发，一定能够相遇并且是入口节点处

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode index1;
        ListNode index2;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                index1=fast;
                index2=head;
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}