首页 > 其他 > 详细

LeetCode 19 Remove Nth Node From End of List 移除倒数第N个节点

时间:2015-05-04 18:17:30      阅读:193      评论:0      收藏:0      [点我收藏+]

题目:

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.

翻译:

给你一个链表,移除倒数第N个节点。

思路:

这道题难度还行,就是一些细节的方面,首先可能链表就一个节点。其次有可能被删除的是第一个节点。最后就是删除该节点后节点的连接。

代码:

	 public ListNode removeNthFromEnd(ListNode head, int n) {
	         if(head==null||(head.next == null && n ==1))
	        	return null;
	        
	        ListNode p = head;
	        ListNode q = head;
	        ListNode pre = head;
	        while(n!=1)
	        {
	        	q = q.next;
	        	n--;
	        }
	        while(q.next!=null)
	        {
	            pre = p;
	        	q = q.next;
	        	p = p.next;
	        }
	        if(pre.next == p.next)
	            head = head.next;
	        else 
	            pre.next = p.next;

	        return head;
	        
	    }
我采用的办法是两个指针p,q,q先遍历到n-1的位置,然后两个指针同时向后遍历,直到q到结尾,此时p为应该删去的。同时来个指针指向p的前一个。

如果p 和pre 指向的是同一个节点,说明此时删去的是 第一个元素。因为上一部q.next==null,这是只要把头结点指向他下一个节点即可。

如果p和pre不等,则直接删除p

LeetCode 19 Remove Nth Node From End of List 移除倒数第N个节点

原文:http://blog.csdn.net/vvaaiinn/article/details/45481801

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!