LeetCode---4.ListEasy

1.题目思路

1. 19.Remove Nth Node From End of List

关键词：双指针

思路：注意题中条件已经说了，考虑的是n是valid，也就是说1<=n<=size。

实际上题目的答案在给出的时候，如果n>实际长度，应该得出等于n取size的结果。

但是测试用例里面都没有大于实际长度的取值。

（1）先遍历一次，计算链表实际长度，

然后计算正向距离，然后再走到欲删除的节点进行删除

（2）两个指针，一个指针先走n步，

然后两个指针一起走，第一个指针走到尾的时候，第二个指针就距离结尾n步。

2. 21.Merge Two Sorted Lists 

思路：本身没有太大的难度，就是同走一个走完了，直接全部给另一个。

简化点，对于第一个元素的处理。

有了第一个元素以后，后面再添加元素直接p->next赋值就好。

这个时候又需要用到dummy元素了。好处是直接就可以处理p->next

并且最后返回，直接返回dummy.next

3. 24.Swap Nodes in Pairs

关键词：三指针（prev,cur1,cur2）

思路：这个关键就是swap两个节点，需要持有3个节点，

被交换的两个节点和它们的前一个节点。

所以有前一个节点，如果不使用dummy的话，又是需要单独处理。

4. 83.Remove Duplicates from Sorted List

关键词:双指针（cur，next）

思路：这个题天生就是比较两个节点，

遇到重复的时候，永远可以取得欲删除节点的前一个节点，dummy节点都不需要。

结束条件是if(next)，由于每比较一次有重复就删除，

所以循环结束都不用再额外处理，返回head即可。

5. 141.Linked List Cycle

关键词：双指针(fast、slow)

思路：两个指针，fast每次比slow多走一步。

假设链表size为N，那么N次以后，如果有环fast肯定和slow相遇。

6. 160.Intersection of Two Linked Lists

关键词：双指针

思路：先分别遍历求得两个链表的长度，注意这里不要走完。走到最后一个节点。

条件为while(p->next)，然后比较两者的最后一个节点，如果不同，直接返回false。

然后让长的那个先走长度差，

然后一起走，停止与相同的地方或者是NULL

while(p != q){

p = p->next;

q = q->next;

}

7. 203.Remove Linked List Elements

关键词：dummy

思路：这个又是删除节点的题目。

那么就还是dummy，然后每次都在前一个节点的时候，判断后面的需不需要被删除。

8. 206.Reverse Linked List

关键词：3指针

思路：先确保至少有2个节点，可以放下3指针不会出现runtime error

然后将第一个的next置为NULL

然后while循环依次将next指向前一个，之所以需要3个指针就是为了将next指向前一个后，

仍然能够将后面一个找到。

最后不要忘了处理最后一个。

9. 234.Palindrome Linked List

关键词：partition、reverse

思路：

（1）借助额外空间。stack。

遍历一遍压入栈，然后再来一次进行比较即可。

（2）不借助额外空间

①找到中间元素。

②将后半部分reverse

③比较

其中找到中间元素，可以遍历一次找到总长度再来。

也可以两个指针一起走，一个一次一步，一个一次两步。

第二个走到NULL，第一个就走到一半。

10. 237.Delete Node in a Linked List

思路：本来我们删除节点是停在前一个节点，然后删除下一个。

由于这里无法达到，被删除的前一个，所以，我们把下一个节点的值copy过来，

然后删除下一个节点即可。

2.题型总结

1.删除节点

要删除一个节点，标准做法是停在一个节点前方。

当然就需要从前面一个得到判断条件。根据条件删除。

比如，删除值等于val的节点

if(p->next->val == val){

ListNode* tmp = p->next;

p->next = p->next->next;

delete tmp

}

当然这样做不仅仅限于删除节点，只要改操作需要由前面搞后面都可以这样。

比如swap pair那道题目。

2.dummy节点

很多时候无论是中间节点还是最后一个有效节点处理方式都是一样的。

比如删除，但是删除第一个节点就不一样了。

因为删除，一般是要先到被删除的节点的前一个节点处。

所以我们可以使用一个dummy节点，它是head的头节点，这样就可以一致地处理所有节点了。

NodeList dummy(-1);

dummy.next = head;

NodeList* cur = &dummy;

....

return dummy.next;

3.多指针

许多情况都需要多指针一起合作

（1）找寻某个链表是否有环？

（2）找寻到两个链表的交点在哪里？

（3）链表中点

（4）距离尾部、某个节点距离N的节点

（5）交换、翻转、删除、等等

3.思考

1.对于删除的ListNode，需要delete