删除链表的倒数第N个结点
解法一
使用双指针
新建一个头节点，避免出现删除头节点出现异常的情况比如[1],1 就会出现问题因为slow.next = slow.next.next 中slow.next会报空指针异常
而新建一个节点后 [newHead,1],1,slow为newhead，那就不会出现空指针异常，并且这个时候的slow就是要删除节点的前一个节点
不需要维护一个pre节点
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null || n == 0) return head; ListNode newHead = new ListNode(0,head); // 有可能删除的是头节点 ListNode slow = newHead; // slow 保存的是需要删除节点的前一个节点 ListNode quick = head; while(quick != null && n != 0){ // 找到比他快n的节点 quick = quick.next; n--; } while(quick != null){ // 同时往后移动 quick = quick.next; slow = slow.next; } slow.next = slow.next.next; return newHead.next; } }
合并两个有序链表
解法一
双指针
list1指向第一个节点，list2指向第二个节点，同时比较大小，谁小就往后移动
如果list1为空了，则把t指向list2，反之同理
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null) return list2; if(list2 == null) return list1; ListNode res = new ListNode(); ListNode t = res; while(list1 != null && list2 !=null){ if(list1.val < list2.val){ t.next = list1; list1 = list1.next; }else{ t.next = list2; list2 = list2.next; } t = t.next; } if(list1 != null)t.next = list1; // 为空直接指向另一个指针 if(list2 != null)t.next = list2; return res.next; } }
相交链表
解法一
使用双指针
ta指向headA，tb指向headB
ta，tb同时往后移，如果为空了，则将当前节点设置为另一个链表的头节点
原理
有相交
A [a1,a2,c1,c2,c3]
B [b1,b2,b3,c1,c2,c3]
则当ta走完A链表时候走的长度为a+c,当b走完B链表时候长度为b+c
则ta指向B，tb指向A
当ta为c1时候走的长度为a+c+b
当tb为c1时候走的长度为b+c+a
没有相交
A[a1,a2]
B[b1,b2,b3]
则A==B的时候只有A == B ==null的时候
所有当ta到达B的末尾null时候走的路程为a+b
tb走到A的末尾null时候走的路程为b+a
所有也可以退出循环
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB ==null) return null; ListNode ta = headA; ListNode tb = headB; while(ta != tb){ ta = ta != null ? ta.next:headB; tb = tb != null ? tb.next:headA; } return ta; } }
解法二
使用哈希集合
把A中节点保存到一个集合，然后循环B中节点，如果集合中有就说明有相交直接返回，如果没有最后返回null
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB ==null) return null; HashSet<ListNode> s = new HashSet<>(); while(headA!=null){ s.add(headA); headA = headA.next; } while(headB!=null){ if(s.contains(headB)) return headB; headB = headB.next; } return null; } }
