双向链表倒置

 

要求：实现一个双向链表的倒置功能（1->2->3 变成 3->2->1)

代码： 

package com.mycom.test;

import java.util.LinkedList;

/**
 * 双向链表节点倒转
 *
 * @author guweiqiang
 * @date 2018年3月28日
 */
public class Test {
	
	/**
	 * 双向链表节点静态内部类
	 */
	public static class LinkedListNode {
		public LinkedListNode prev; // 前一个节点
		public LinkedListNode next; // 后一个节点
		public int value; // 当前节点值
		
		public LinkedListNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 双向链表节点倒转
	 */
	private static LinkedListNode reverseNode(LinkedListNode node){
		LinkedListNode prev = null;
		LinkedListNode next = null;
		
		while(node!=null) {
			next = node.next;
			node.next = prev;
			node.prev = next;
			prev = node;
			node = next;
		}
		
		return prev;
	}
	
	/**
	 * 双向链表倒置
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static LinkedList<LinkedListNode> reverseList(LinkedList<LinkedListNode> linkedList){
		LinkedList<LinkedListNode> result = new LinkedList();
		for (int i=linkedList.size(); i>0; i--) {
			result.add(reverseNode(linkedList.get(i-1)));
		}
		return result;
	}

	/**
	 * main 测试
	 * @param args
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static void main(String[] args) {
		// 原始双向链表
		LinkedList<LinkedListNode> linkedList = new LinkedList();
		// 第1种情况：节点是有序的
		for (int i=1; i<6; i++) {
			linkedList.add(new LinkedListNode(i));
		}
//		// 第2种情况：节点是无序的
//		linkedList.add(new LinkedListNode(2));
//		linkedList.add(new LinkedListNode(3));
//		linkedList.add(new LinkedListNode(1));
//		linkedList.add(new LinkedListNode(5));
//		linkedList.add(new LinkedListNode(4));
//		linkedList.add(new LinkedListNode(6));
		System.out.println("before reverse:");
		for(LinkedListNode node : linkedList) {
			System.out.print(node.value + " ");
		}
		
		// 倒转之后的双向链表
		LinkedList<LinkedListNode> result = reverseList(linkedList);
		System.out.println("\nafter reverse:");
		for(LinkedListNode node : result) {
			System.out.print(node.value + " ");
		}
	}

}

 以上是使用jdk自带的双向链表实现的，如果要自己实现一个双向链表呢？

 

自定义双向链表：

package com.mycom.test.linkedlist;

/**
 * 自定义双向链表
 *
 * @author guweiqiang
 * @date 2018年3月29日
 */
public class LinkedList<E> {
	
	private LinkedListNode<E> head; // 双向链表的头结点
	private int size; // 双向链表的大小
	private transient int modCount = 0; // 双向链表被修改的次数
	
	public LinkedList() {

	}
	
	public LinkedList(E e) {
		head = new LinkedListNode<E>(e); // 双向链表的头结点
		size++;
        modCount++;
	}
	
	/**
	 * 往双向链表里添加一个元素
	 * @param e 待添加的元素
	 * @return true：添加成功；false：添加失败
	 */
	public boolean add(E e) {
	    return addLast(e); // 默认将元素添加到双向链表的末尾
	}

	/**
	 * 在双向链表指定位置插入一个元素
	 * @param index 指定位置的下标
	 * @param e 待插入的元素
	 * @return true：插入成功；false：插入失败
	 */
	public boolean add(int index, E e) {
		LinkedListNode<E> node = this.getLinkedListNode(index); // 获取指定下标位置的节点
		addBefore(new LinkedListNode<E>(e), node); // 将上述节点添加到指定位置节点的前面
	    return true;
	}
	
	/**
	 * 往双向链表里添加第一个元素
	 * @param e 待添加的元素
	 * @return true：添加成功；false：添加失败
	 */
	public boolean addFirst(E e) {
		head = new LinkedListNode<E>(e);
        size++;
        modCount++;
	    return true;
	}

	/**
	 * 将元素添加到双向链表的最后
	 * @param e 待添加的元素
	 * @return true：添加成功；false：添加失败
	 */
	public boolean addLast(E e) {
		addBefore(new LinkedListNode<E>(e), head); // 将元素添加到头结点之前
	    return true;
	}

	/**
	 * 移除双向链表的元素（默认移除双向链表最后一个元素）
	 * @return true：移除成功；false：移除失败
	 */
	public boolean remove() {
		return removeLast();
	}
	
	/**
	 * 移除双向链表的尾结点元素
	 * @return true：移除成功；false：移除失败
	 */
	public boolean removeLast() {
		this.removeNode(head.prev);
		return true;
	}
	
	/**
	 * 获取指定位置的元素
	 * @param index 指定位置下标
	 * @return 元素
	 */
	public LinkedListNode<E> get(int index) {
	    return getLinkedListNode(index);
	}

	/**
	 * 判断双向链表中是否已经包含了该节点元素
	 * @return true：包含；false：不包含
	 */
	public boolean contain(LinkedListNode<E> e) {
        if (e == null) {
        	// 从链表的表头开始查找，如果找到了就返回true
            for (LinkedListNode<E> node = head; node != null; node = node.next) {
                if (node.e == null) { // 找到为null的元素
                	return true;
                }
            }
        } else {
        	// 从链表的表头开始查找，如果找到了就返回true
            for (LinkedListNode<E> node = head; node != null; node = node.next) {
                if (e.equals(node.e)) { // 两个元素的equal比较如果为true，则返回true
                    return true;
                }
            }
        }
        return false;
	}
	
	/**
	 * 清空双向链表
	 */
	public void clear() {
		for (LinkedListNode<E> node = head; node != null; node = node.next) {
			node.e = null;
			node.next = null;
			node.prev = null;
        }
        head = null;
        size = 0;
        modCount++;
	}
	
	/**
	 * 获取双向链表的大小
	 * @return 双向链表的大小
	 */
	public int size() {
	    return this.size;
	}
	
	/**
	 * 打印链表里的元素
	 */
	public String toString(LinkedList<E> list) {
		StringBuffer str = new StringBuffer("");
		for (int i=0; i<list.size; i++) {
			str.append(list.get(i).e.toString() + " ");
		}
		return str.toString();
	}
	
	/**
	 * 双向链表所有节点元素倒转
	 * @param oldList 倒转之前的linkedList
	 * @return 倒转之后的linkedList
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public LinkedList<E> reverseList(LinkedList<E> oldList){
		LinkedList<E> resultList = new LinkedList(oldList.get(oldList.size()-1).e);
		for (int i=oldList.size()-1; i>0; i--) {
			resultList.add(this.reverseNode(oldList.get(i-1)).e);
		}
		return resultList;
	}
	
	/**
	 * 双向链表节点倒转
	 * @param node 待倒转的节点
	 */
	private LinkedListNode<E> reverseNode(LinkedListNode<E> node){
		LinkedListNode<E> prev = null;
		LinkedListNode<E> next = null;
		
		next = node.next;
		node.next = prev;
		node.prev = next;
		prev = node;
		node = next;
		
		return prev;
	}
	
	/**
	 * 在当前节点前面插入一个节点
	 * @param newNode 要添加的新节点
	 * @param node 当前节点
	 */
	private void addBefore(LinkedListNode<E> newNode, LinkedListNode<E> node) {
	    newNode.next = node;
	    newNode.prev = node.prev;
	    newNode.next.prev = newNode;
	    newNode.prev.next = newNode;
	    size++;
        modCount++;
	}
	
	/**
	 * 在当前节点后面插入一个节点
	 * @param newNode 要添加的新节点
	 * @param node 当前节点
	 */
	@SuppressWarnings("unused")
	private void addAfter(LinkedListNode<E> newNode, LinkedListNode<E> node) {
	    newNode.prev = node;
	    newNode.next = node.next;
	    newNode.next.prev = newNode;
	    newNode.prev.next = newNode;
	    size++;
        modCount++;
	}
	
	/**
	 * 移除指定位置的节点元素
	 * @param node 待移除的节点
	 */
	private void removeNode(LinkedListNode<E> node) {
		node.prev.next = node.next;
	    node.next.prev = node.prev;
	    node.prev = null;
	    node.next = null;
	    size--;
        modCount++;
	}
	
	/**
	 * 获取双向链表中指定位置的元素
	 * @param index 指定位置下标
	 * @return 元素
	 */
	private LinkedListNode<E> getLinkedListNode(int index) {
		// 判断下标是否越界，如果越界则抛出异常
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException();
		}
		
		// 从链表的表头开始遍历，遍历每一个节点，直到下标为index所在的元素
		LinkedListNode<E> node = head;
		for(int i=0; i<index; i++) {
			node = node.next;
		}
		
		return node;
	}
	
	/**
	 * 双向链表节点静态内部类
	 */
	public static class LinkedListNode<E> {
		public LinkedListNode<E> prev = this; // 前一个节点
		public LinkedListNode<E> next = this; // 后一个节点
		public E e; // 当前节点元素
		
		public LinkedListNode(E e) {
			this.e = e;
		}
	}

}

 测试用例：

package com.mycom.test.linkedlist;

/**
 * 测试双向链表节点倒转
 *
 * @author guweiqiang
 * @date 2018年3月29日
 */
public class Test1 {
	
	/**
	 * 测试有序节点倒转
	 */
	private void testOrderNum(){
		// 原始双向链表，初始化head节点为1
		LinkedList<Integer> linkedList = new LinkedList<Integer>(1);
		// 节点是有序的
		for (int i=1; i<5; i++) {
			linkedList.add(Integer.valueOf(i+1));
		}
		System.out.println("before reverse:");
		for (int i=0; i<linkedList.size(); i++) {
			System.out.print(linkedList.get(i).e.intValue() + " ");
		}
		
		// 倒转之后的双向链表
		LinkedList<Integer> resultList = new LinkedList<Integer>().reverseList(linkedList);
		System.out.println("\nafter reverse:");
		for (int i=0; i<resultList.size(); i++) {
			System.out.print(resultList.get(i).e.intValue() + " ");
		}
	}
	
	/**
	 * 测试无序节点倒转
	 */
	private void testNonOrderNum(){
		// 原始双向链表，初始化head节点为2
		LinkedList<Integer> linkedList = new LinkedList<Integer>(2);
		// 节点是无序的
		linkedList.add(1);
		linkedList.add(3);
		linkedList.add(5);
		linkedList.add(4);
		System.out.println("before reverse:");
		for (int i=0; i<linkedList.size(); i++) {
			System.out.print(linkedList.get(i).e.intValue() + " ");
		}
		// 倒转之后的双向链表
		LinkedList<Integer> resultList = new LinkedList<Integer>().reverseList(linkedList);
		System.out.println("\nafter reverse:");
		for (int i=0; i<resultList.size(); i++) {
			System.out.print(resultList.get(i).e.intValue() + " ");
		}
	}
	
	/**
	 * main 
	 * @param args
	 */
	public static void main(String[] args) {
		Test1 test = new Test1();
		test.testOrderNum();
		test.testNonOrderNum();
	}

}