Day9 |删除链表倒数第N个节点 相交链表

第九天明天准备回顾总结一下之前的日记嘞。题目删除链表的倒数第 N 个结点LeetCode 19描述给你一个链表删除链表的倒数第n个结点并返回链表的头结点。解法快慢指针定义两个指针相差x步当快指针走到最后节点时慢指针刚好指向删除节点。public class Solution { public ListNode RemoveNthFromEnd(ListNode head, int n) { ListNode reHead new ListNode(-1); reHead.next head; ListNode poi_1 reHead; ListNode poi_2 reHead; //拉开n的差距 for(int i 0;i n;i){ poi_1 poi_1.next; } while(poi_1.next ! null){ poi_1 poi_1.next; poi_2 poi_2.next; } poi_2.next poi_2.next.next; return reHead.next; } }题目相交链表描述找到两个单链表相交的起始节点。如果不相交返回null。解法一哈希表把一个列表的所有节点都存进哈希表然后遍历另一个列表第一个在哈希表中出现的节点就是相交点。public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { Hashtable table new Hashtable(); ListNode poi1 headA; while (poi1 ! null) { table.Add(poi1, poi1.val); poi1 poi1.next; } ListNode poi2 headB; while (poi2 ! null) { if (table.ContainsKey(poi2)) { return poi2; } poi2 poi2.next; } return null; } }解法二双指针public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode p1 headA; ListNode p2 headB; while (p1 ! p2) { p1 p1 ! null ? p1.next : headB; p2 p2 ! null ? p2.next : headA; } return p1; // 要么是交点要么是 null } }一开始我尝试过不处理走到末尾的指针让它继续取next结果空引用报错。于是让指针“跳到另一条路”重新跑。刚开始还担心会不会无限循环后来画图算了一下总路程一样最终一定会同时变成null不存在死循环。这个解法让我想起一点歌词嘞。。。我吹过你吹过的晚风是否看过同样 风景像扰乱时差留在错位时空终是空 是空