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，不存在死循环。

这个解法让我想起一点歌词嘞。。。
我吹过你吹过的晚风
是否看过同样 风景
像扰乱时差留在错位时空
终是空 是空