找到单向链表的倒数第N个元素

找到单向链表的倒数第N个元素，如何在空间时间消耗上做到最小。

通常的做法是遍历一边得到长度，然后遍历第二遍，取得对应元素。
这种做法时间消耗是链表长度的2倍 - N。

或者消耗空间节省时间的方式，创建数组，遍历链表，将元素放入数组中。
这种做法时间消耗和空间消耗都是链表长度。

那么有没有更好的方式。

1.创建一个指针。
2.遍历链表，当顺序是2N的倍数时，用指针记录位置。
3.当遍历结束时，指针之后（链表长度 % 2N - N）个元素即是单向链表的倒数第N个元素。
时间消耗是链表长度 + （链表长度 % 2N - N）
空间消耗是指针的大小。

声明变量 point,
声明变量 current = 链表第一个元素
声明变量 size = 0
while（current != null）{
  size++
  if ( size % 2n==0) {
    point=current
  }
current = current -> next
}

声明变量 result,
for (i=0; i < size % 2n - n; i++) {
  result = point -> next
}
打印 result

用得着这么麻烦么...直接记录size - N的引用就可以了...

声明变量 result,
声明变量 current = 链表第一个元素
声明变量 size = 0
while（current != null）{
  size++
  if ( size - N > -1) {
    result=current
  }
  current = current -> next
}

打印result.

我的意思是一共10个元素，找到倒数第3个元素，即第8个元素。

我明白你的意思，我上面的算法是有点问题，但思路是可以的，伪代码修改如下：

 

声明变量 result, 
声明变量 current = 链表第一个元素 
声明变量 size = 0 
while（current != null）{ 
  size++ 
  if ( size - N > -1) { 
    result= result -> next 
  } 
  current = current -> next 
} 

打印result.

 

实现代码如下：

 

 

 

public class List {
	
	public List nextList;
	public String data;

	public static void main(String[]args) {
		//构造测试数据,10个元素
		List root = new List();
		root.data = "第1个元素";
		
		List current = root;
		for(int i =2; i < 11;i++) {
			List newList = new List();
			newList.data = "第" + i + "个元素";
			current.nextList = newList;
			current = current.nextList;
		}
		
		//取出倒数第三个元素
		List list = calculate(root,3);
		System.out.println(list.data);
	}

	public static List calculate(List root, int i) {
		List current = root;
		List result = current;
		int size = 0;
		
		while(current.nextList != null) {
			size ++;
			if(size - i >  -1) {
				result = result.nextList;
			}
			current = current.nextList;
		}
		
		return result;
	}

}

 

 

 

倒数第一个，即比最后指针慢一步，同理倒数第N个，即比最后一个慢N步。

public class Node {

	private String info = "";
	
	public Node next;
	
	public Node(String info) {
		this.info = info;
		next = null;
	}
	
	public void display() {
		System.out.print(info + " ");
	}
}

public class LinkList {

	private Node root;
	private Node curNode;
	
	public void add(String info) {
		Node node = new Node(info);
		if(null == root) {
			root = node;
			curNode = root;
		} else {
			curNode.next = node;
			curNode = node;
		}
	}
	
	public void display() {
		Node node = root;
		while(null != node) {
			node.display();
			node = node.next;
		}
	}
	
	
	public Node getLastAt(int i) {
		Node node = root;
		Node iNode = root;
		int size = 0;
		while(null != iNode) {
			size++;
			if(size > i) {
				node = node.next;
			}
			iNode = iNode.next;
		}
		return node;
	}
	
}

public class MainTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkList ll = new LinkList();
		ll.add("A");
		ll.add("B");
		ll.add("C");
		ll.add("D");
		ll.add("E");
		
		ll.display();
		System.out.println("----");
		ll.getLastAt(7).display();
		
	}

}

为何不用双向链表呢？