LeetCode 链表：21合并两个有序链表 19删除链表的倒数第N个节点
21合并两个有序链表
思路：
这个题目搞出来了，但是由于没有用哨兵这个技巧，很不简洁。
思路很简单，新的链表有一个头head，有一个尾end.遍历链表，while(p1!=null&p2!=null)，比较出p1和p2中最小的，把这个最小的添加到尾部end的后面作为新的尾部，然后p1或者p2指针后移一位。等到遍历完，需要看p1或者p2是否不为null，如果不为null，应该将其添加到尾部。
问题来了，新链表的头部在遍历之前是不确定的（为p1和p2中较小的一个），而且这同时也是第一次遍历时新链表的尾部，从而尾部也无法确定。导致需要把第一次循环单拿出来做确定初始的头和尾。
第二个问题：第一次遍历还不能直接比较p1和p2的大小，因为p1可能为空。。。所以还要加一个判断。
先看一下一开始写的渣渣代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode res,end,p1=l1,p2=l2; if(l1==null) { return l2; } else if(l2==null) { return l1; } if(l1.val<=l2.val) { res=l1; end=l1; p1=p1.next; } else { res=l2; end=l2; p2=p2.next; } while(p1!=null&p2!=null) { if(p1.val<=p2.val) { end.next=p1; end=p1; p1=p1.next; } else { end.next=p2; end=p2; p2=p2.next; } } if(p1==null) { end.next=p2; } else if(p2==null) { end.next=p1; } return res; } }
一开始代码
哨兵的想法很好
先指定一个prehead，当然它也是新链表的初始尾。这样就可以不用写那些多余的代码了，第一次循环和其他循环都一样，只用end.next=p1和p2中取小就行了。最终结果的头就是prehead.next
更加巧妙的是，这样还能避免p1或者p2为null的问题。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode preHead=new ListNode(0); ListNode end=preHead; while(l1!=null&l2!=null) { if(l1.val<=l2.val) { end.next=l1; end=end.next; l1=l1.next; } else { end.next=l2; end=end.next; l2=l2.next; } } end.next=(l1==null)?l2:l1; return preHead.next; }
此题还有递归方法，日后再说。
19删除链表的倒数第N个节点
思路：这道题做出来了，很快就有了思路，写出来后碰了个null.next的问题，之后也解决了
要找倒数第N节点，必然要找最后一个节点。但是由于单向链表是“开弓没有回头箭”，怎么在找到末尾节点时找到其前第n个节点就是问题。
之前碰到过的大量双指针问题迅速给了我思路，让第一个指针先走n步，再两个节点一起往前走就行了。多么简洁的解题思路！
理清一下两个指针的关系：先遍历n次，这时p1 p2距离为n。
当p1为null时，p2为倒数第n个节点，但是我们要删除倒数n节点显然要找的是倒数第n+1个节点,p(倒数n+1).next=p(倒数n+1).next.next。
当p1为最后一个节点时，p2为倒数第n+1个节点，显然这样更好。
因此，这里的第二次循环的条件设置为while(p1.next!=null)，最终指针停留在最后一个节点。
也想过增加距离然后用p1=null判定，但这会让第一次循环时第一个节点更容易越界。
下一个问题来了，假如长度为length，n也为length。第一次循环后p1指向null，第二次循环一开始就会是null.next错误，因此还应在第一次循环后再加一个判断，判断是否p1=null，这等价于n=lenth，只用删除第一个节点就行。
我最终代码如下
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode p1=head,p2=head; for(int i=0;i<n;i++) { p1=p1.next; } if(p1==null) {return head.next;} while(p1.next!=null) { p1=p1.next; p2=p2.next; } p2.next=p2.next.next; return head; } }
LeetCode官方解法：
诶，碰到这种null.next，应该要想到dummy这个技巧的！
简而言之，我们只需要p1和p2拉开n的距离，但跑道太短，先走n步会撞墙，所以大家先都倒退一步再开始走就行了。
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; } 作者：LeetCode 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
PS：看来LeetCode也会出提交的bug，明明都是O1的空间复杂度，只战胜了百分之5的空间复杂度可还行。剩下百分之95怕不是用的量子计算机（滑稽）。