关于单链表、双向列表的一些算法

首先给出数据定义的结构

单链表

/**
 * 链表
 */

public class LinkTable {
  public LinkTable next;
  public String name;

  public void setName(String name) {
    this.name = name;
  }

  public LinkTable(String name) {
    this.name = name;
  }
}

1.单链表的逆序反转

package zong.xiao.mi.demosource.java;

/**
 * Created by mi on 2017/3/9.
 */

public class 单链表的倒序 {

  public static void main(String[] a) {
    LinkTable linkTable = LinkTableReverse2(getLinkTable());
    print(linkTable);

  }

  public static LinkTable getLinkTable() {
    LinkTable A = new LinkTable("A");
    LinkTable B = new LinkTable("B");
    LinkTable C = new LinkTable("C");
    LinkTable D = new LinkTable("D");
    LinkTable E = new LinkTable("E");
    A.next = B;
    B.next = C;
    C.next = D;
    D.next = E;
    return A;
  }

  /**单链表逆序（反转）
   * 非递归
   * 1.把root的next拿出来
      2.把root.next赋值 
      3.把头部newRoot存起来
      4.更换root为为head
   * @param root
   */
  public static void LinkTableReverse(LinkTable root) {
    print(root);
    LinkTable newRoot = null;
    while (root != null) {
      LinkTable next = root.next;
      root.next = newRoot;
      newRoot = root;
      root = next;
    }
    print(newRoot);
  }

  /**
   * 递归 递归的思想就是找到最后一个节点 返回到上一层，
   * 让root.next.next=root 回溯 root.nex=null;
   * 
   * @param root
   * @return
   */
  public static LinkTable LinkTableReverse2(LinkTable root) {
    LinkTable newRoot = null;

    if (root == null || root.next == null) {
      return root;
    }
    newRoot = LinkTableReverse2(root.next);
    root.next.next = root;
    root.next = null;
    return newRoot;

  }

单链表相邻节点反转 A-B-C-D 输出 B-A-D-C

/**
   * 链表相邻两元素反转
   * 比如A-B-C-D-E输出B-A-D-C-E
   * 
   * @param root
   * @return
   */
  public static LinkTable borderReverse(LinkTable root) {

    if (root == null || root.next == null) return root;
    LinkTable curr = root;
    LinkTable next;
    LinkTable pre = null;
    while (curr != null && curr.next != null) {

      if (pre != null) {
        pre.next = curr.next;
      } else {
        root = curr.next;
      }
      pre = curr;
      next = curr.next.next;
      curr.next.next = curr;
      curr.next = next;
      curr = curr.next;
    }
    return root;

  }
  public static void print(LinkTable root) {
    while (root != null) {
      System.out.print(root.name);
      System.out.print("--");
      root = root.next;
    }
    System.out.println();
  }
}

双向链表

public class Node {

  public Node pre;
  public Node next;
  public int data;

  public Node(Node pre, Node next, int data) {
    this.pre = pre;
    this.next = next;
    this.data = data;
  }

  public static void printNode(Node node) {
    Node n = node;
    while (n != null) {
      System.out.println(n.data);
      n = n.next;
    }

  }
}

双向链表的反转

 public Node reverse(Node node) {
    Node n = node, pre = null;
    while (n != null) {
      Node next = n.next;
      n.next = pre;
      n.pre = next;
      pre = n;
      n = next;
    }
    return pre;
  }