【算法】删除单链表的倒数第N个结点

Description

Given a linked list, remove the nth node from the end of list and return its head. *For example, * Given linked list: 1->2->3->4->5, and n = 2. * After removing the second node from the end, * the linked list becomes 1->2->3->5. *Note: * Given n will always be valid. * Try to do this in one pass.

这是Leetcode中的一道题，剑指offer中是查找到单链表的倒数第N个结点，题目类似。

解题思路

采用两个指针，first和slow，first先后移N个结点，然后slow和first同时向后移动，因为两个指针相差N个结点，所以当first.next==null，slow现在指的就是倒数第N个结点的前驱，所以直接利用slow.next = slow.next.next，删除这个节点。 代码如下：

/** * @ congrisheng * @ 2017-3-13 * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public ListNode removeNthFromEnd(ListNode head, int n){ if(head == null || head.next == null){ return null; } ListNode slow = head; ListNode first = head; for(int i = 0; i < n; i++){ first = first.next; } if(fast == null){ head = head.next; return head; } while(first.next != null){ slow = slow.next; first = first.next; } slow.next = slow.next.next; return slow; }

From《剑指offer》Page13