Leetcode_19_Remove Nth Node From End of List

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/41778305

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.

思路:

(1) 题意为移除链表倒数第N个元素。

(2) 首先,对链表进行判空,空则返回null(要注意的是还需对N是否在链表大小范围之内进行判断)。

(3) 其次,本文主要用栈来进行操作(这里暂不考虑效率和代码简短问题,仅仅提供一种解题思路)。本文的思想是创建两个栈,一个栈是来存储整个链表中的节点,另一个栈是来存储去除倒数第N个元素后剩余的节点,运用栈先进后出的特性进行操作并得到结果。

(4) 最后,先遍历链表,将链表中节点存入栈s1中;然后,依次从栈s1中pop元素,并设置count来记录pop元素的个数,如果得到count != N,则将pop出的元素加入栈s2中,并将该元素的next设置为空(需要去除节点间的顺序,从栈中pop出时就带有顺序),如果count==N,则说明pop出的元素为待移除的元素,不将其加入s2中;最后,依次从栈s2中pop出元素,将其按pop出的顺序组合起来即为结果。

(5)这里主要考虑到栈的特性:先进后出。能够想到这一点,在不考虑性能等限定的情况下能够很容易解出答案。

算法代码实现如下所示:

public static ListNode removeNthFromEnd(ListNode head, int n) {
	if (head == null)
		return null;

	Stack<ListNode> s1 = new Stack<ListNode>();// 将当前链表所有节点压入栈中
	Stack<ListNode> s2 = new Stack<ListNode>();// 移除指定元素后的栈
	int count = 0;
	while (head != null) {
		s1.push(head);
		head = head.next;
	}

	while (s1.size() != 0) {
		ListNode pop = s1.pop();
		pop.next = null;
		count++;
		if (count == n) {
			continue;
		} else {
			s2.push(pop);
		}
	}

	ListNode result = null;
	ListNode flag = null;
	while (s2.size() != 0) {
		ListNode pop = s2.pop();
		if (result == null) {
			result = pop;
			flag = result;
			continue;
		}
		flag.next = pop;
		flag = flag.next;
	}
	return result;
}
上一篇:一步一步开发Game服务器(三)加载脚本和服务器热更新(二)完整版


下一篇:Git配置用户信息和SSH