代码随想录--链表--删除链表第n个节点题型、链表相交题型

删除链表第n个节点题型

链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点 (opens new window)

这道题我一开始想的是，倒数第n个节点，链表不方便往前找，那就从链表头结点开始找链表长度减n，这时候就是其要删除的前一个节点，然后删除操作即可。
思路应该是没有问题，不过有一点，就是链表长度，不是像数组那样直接数组.size()就能知道长度，链表需要做循环，循环完整个链表才能知道链表长度，相比下面的解法多了个循环，所以还是用下面的解法好。

利用双指针找链表中倒数第n个节点。
让快慢指针相差n个节点，然后再一起往右移，当快指针移到null时，停下来，这时候慢指针刚好指向要删除的节点处，利用慢指针操作删除操作即可。但是因为是删除，所以需要操作的是要删除节点的前一个节点，所以快慢指针应该相差n+1个节点。
这道题主要就是怎么找链表中的倒数第n个节点，并且要注意操作指针是指向倒数第n个节点的前一个节点(因为删除操作要知道前一个节点)，用虚拟结点，就能统一删除操作，不用分头结点和非头节点怎么分别处理，所以我们用虚拟头结点。

大致代码套路：

new dummyhead;
fast=dummyhead;
slow=dummyhead;
n++;
while(n--&&fast!=null){
            fast=fast->next;
}
while(fast!=null){
       fast=fast->next;
       slow=slow->next;
}
slow->next=slow->next->next;
return dummyhead->next;

 

链表相交题型

我理解错了，
注意，题目是给出两个已经相交的链表，然后让你找出相交部分的初始节点。
我以为给两个链表，然后后面如果全部相同就相交，然后就输出相交的第一个节点。
我说怎么例1中8之前明明有个1，为啥不是从1开始相交呢，因为题目已经给好了呀。
哦～所以说卡哥才说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。题目是已经给好相交的了，所以如果两链表的两指针相等(指向同一个节点)，则说明节点相交了。不要想太多，题目给的就是相交后，两个链表后面都是相交的了，即后面长度是一样长的了。

 那为啥要末尾位置对齐呢？
注意你要找的是两个指针指向同一个节点即相等的情况。
那如果两指针至各自末尾长度不相等的时候，你就开始一起移动，是找不到相交点的，如上图，curA从a1开始，curB从b1开始，那curB走到c1时curA已经到c2了，就错了。所以应该让长的那个链表的指针走到距离末尾长度等于短的链表指针距离末尾长度后，如下图，才开始一起移动指针并且判断是否相等。

 

注意，由于不知道两个链表那个是最长的，所以通过
if(lengthB>lengthA){
            swap(lengthA,lengthB);
            swap(curA,curB);
        }
来固定curA为最长链表的头，lengthA为最长链表的长度。
本来是curA指向headA的嘛，lengthA是表示headA所属的长度。
如果链表A的是最长的那就继续让curA为其链表的头，lengthA为其链表的长度。
如果链表B的是最长的那就交换，即交换curAB让curA指向链表B，交换lengthAB让lengthA表示链表B的长度。