单链表 - 单链表的反转 - 腾*和*迅的面试题

说明

运行时间O(N)
首先，弄一个简单的单链表，包括

1. 首尾节点、大小
2. add()、show()、Node静态内置类

然后，添加reverse()，实现反转功能
最后，写测试方法，@Test调用

<mark>其中，reverse的实现思路为：</mark>
（转向操作）

1. 创建 $indexNodeNextShould$indexNodeNextShould，指向上一个节点的信息
2. 创建 $indexNextNode$indexNextNode ，指向下一个节点的信息
3. $当前节点$当前节点连接 $indexNodeNextShould$indexNodeNextShould

（为下次循环做准备）

4. $indexNodeNextShould$indexNodeNextShould指向 $当前节点$当前节点作为上一个节点
5. $当前节点$当前节点指向 $indexNextNode$indexNextNode （当前节点后移）

$google$google

代码实现

简单的单链表

package cn.edut.test;

import org.junit.Test;

public class MySingleLinkedList<T> {
	private Node<T> first ; 
	private Node<T> last ; 
	private int size;
	public boolean add(T e) {
		if(first==null) 
		{//第一元素添加
			first =new Node<T>(e,null);
			last = first;
		}else 
		{ //非第一次
			last.next = new Node<T>(e, null);
			last = last.next;
		}
		size++;
		return true;
	}
	
	public void show() {
		System.out.print("[");
		Node<T> next = first; 
		for(int index=0 ; index<size-1 ; index++) {
			System.out.print(next.elementDate+", ");
			next = next.next;
		}
		System.out.println(last.elementDate+"]");
	} 
	
	private static class Node<T>{
		private Node<T> next ;
		private T elementDate  ;
		public  Node(T e ,  Node<T> nex) {
			this.elementDate = e ; 
			this.next = nex;
		}
	}
}

reverse()

public void reverse() {

		//没初始化，只有一个值
		if(first==null||first==last) 
		{
			return ;
		}
		//记录当前操作节点
		Node<T> indexNode = first;
		//存储上一个节点
		Node<T> indexNodeNextShould = null;
		while(true) {
			//记录下一节点
			Node<T> indexNextNode = indexNode.next;
			//当前节点的next==上一个节点
			indexNode.next = indexNodeNextShould ;
			//存储上一个节点记录往后移
			indexNodeNextShould = indexNode;
			
			if(indexNode == last) {
				break;
			}else {
				//操作节点后移
				indexNode = indexNextNode;
			}
		}
		//首尾节点指向调转
		Node<T> temp = last;
		last = first ; 
		first = temp ;
	}

@Test调用

/** * 测试 创建、add、清除、reverse、Iterator */
	@Test
	public void test01() {
		//弄几个数据进去
		MySingleLinkedList<Integer> mll = new MySingleLinkedList<Integer>();
		while(mll.size<10) {
			mll.add(mll.size);
		}
		System.out.print("调转前：");mll.show();
		//数据调转
		mll.reverse();
		System.out.print("调转后：");mll.show();
	}

完整代码

package cn.edut.test;

import org.junit.Test;

public class MySingleLinkedList<T> {
	
	/** * 测试 创建、add、清除、reverse、Iterator */
	@Test
	public void test01() {
		//弄几个数据进去
		MySingleLinkedList<Integer> mll = new MySingleLinkedList<Integer>();
		while(mll.size<10) {
			mll.add(mll.size);
		}
		System.out.print("调转前：");mll.show();
		//数据调转
		mll.reverse();
		System.out.print("调转后：");mll.show();
	}
	
	
	private Node<T> first ; 
	private Node<T> last ; 
	private int size;
	
	public boolean add(T e) {
		if(first==null) 
		{//第一元素添加
			first =new Node<T>(e,null);
			last = first;
		}else 
		{ //非第一次
			last.next = new Node<T>(e, null);
			last = last.next;
		}
		size++;
		return true;
	}
	
	public void show() {
		System.out.print("[");
		Node<T> next = first; 
		for(int index=0 ; index<size-1 ; index++) {
			System.out.print(next.elementDate+", ");
			next = next.next;
		}
		System.out.println(last.elementDate+"]");
	} 
	
	private static class Node<T>{
		private Node<T> next ;
		private T elementDate  ;
		public  Node(T e ,  Node<T> nex) {
			this.elementDate = e ; 
			this.next = nex;
		}
	}
	
	public void reverse() {

		//没初始化，只有一个值
		if(first==null||first==last) 
		{
			return ;
		}
		//记录当前操作节点
		Node<T> indexNode = first;
		//存储上一个节点
		Node<T> indexNodeNextShould = null;
		while(true) {
			//记录下一节点
			Node<T> indexNextNode = indexNode.next;
			//当前节点的next==上一个节点
			indexNode.next = indexNodeNextShould ;
			//存储上一个节点记录往后移
			indexNodeNextShould = indexNode;
			
			if(indexNode == last) {
				break;
			}else {
				//操作节点后移
				indexNode = indexNextNode;
			}
		}
		//首尾节点指向调转
		Node<T> temp = last;
		last = first ; 
		first = temp ;
	}
}

测试结果