每日三题-合并两个有序链表、相交链表、删除链表的第N个节点
👨💻个人主页： 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇♂️ 📒 本文来自专栏： 算法 🌈 算法类型：Hot100题 🌈
每日三题
删除链表的倒数第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;
}
}腾讯云开发者
