单链表。 主要任务是找到倒数第N个结点。
一、很容易想到是先遍历一次，得到链表总长度allCount，allCount - N 就是要删除结点的前置结点。为了简单，可以添加一个头结点dummy。
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); //添加头节点 int countAll = 0; ListNode hCount = dummy; while(hCount.next != null) { hCount = hCount.next; countAll++; } int desDeletePre = countAll - n; ListNode hd = dummy; desDeletePre--; while(desDeletePre>=0){ hd = hd.next; desDeletePre--; } //删除后面的 hd.next = hd.next.next; return dummy.next; }
二、双指针法。一个指针先走N步，另一个指针此时出发，先走的指针到达结尾时，后面的指针离结尾还有N步。
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); //添加头节点 ListNode fast = dummy; ListNode slow = dummy; int count = n; //fast先走n步 while(count>0){ fast = fast.next; count--; } //slow也开始 while(fast.next!= null) { fast = fast.next; slow = slow.next; } //删除 slow.next = slow.next.next; return dummy.next; }
两个算法的时间复杂度都是O(N)。
