删除单链表倒数第N个节点

删除正数第N个节点,很简单,那么删除倒数的第N个节点呢?

先算出 节点总数sum,再正向移动sum – N次吗?不是的。

用快慢指针的方式会很简单

 

/**
 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.
 */
public class RemoveNthNodeFromEndOfList {
//用两个指针相差N个节点的方法,一个快指针,一个慢指针寻找倒数第N个节点
    public ListNode removeNthFromEnd(ListNode h, int n) {

        ListNode pEnd = h;//当pEnd指向null的时候,pNthFromEnd指向了倒数第N个节点
        ListNode pNthFromEnd = h;//指向倒数第N个节点
        ListNode pre = new ListNode(0);//h前加一个头,pre指向pNthFromEnd前一个节点
        pre.next = h;
        ListNode pHead = pre;

        while (pEnd != null && n-- != 0){//向后遍历N次
            pEnd = pEnd.next;
        }
        while (pEnd != null) {//找到倒数Nth节点
            pEnd = pEnd.next;
            pre = pNthFromEnd;
            pNthFromEnd = pNthFromEnd.next;
        }
        pre.next = pNthFromEnd.next;
        pNthFromEnd.next = null;

        return pHead.next;
    }
}
Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>