链表翻转

要点

分为两种方式，分别是头插法和就地翻转

链表翻转示意图.png

区别

• 头插法两个指针随着遍历往后，而且声明一个新的头
• 就地反转头用已存在的，一个指针随着遍历往后，另一个指针不变始终指向第一个（即翻转后的最后一个），但是该节点会随着遍历往后移（即变的是改节点而非指针）

头插法（声明新链表，把原先的逐个加到新的里面）

• 声明一个空的头，声明两个指针，三个变量
• 变量1指向要插入的节点
• 变量2指向下一个节点，防止变量1指向的节点插入时断链
• 随着遍历（即在循环中），两个指针往后移动

就地翻转

• 新声明两个变量，头用原来的，一共三个变量
• 变量1指向头结点，用来指向第一个变量，也即反转后的最后一个元素，随着遍历不变（即在循环中不变），变的是节点相对位置而非该指针变量
• 变量2指向头结点下一个节点，随着遍历指针往后走，判空条件为该变量为空
• 过出来的节点也是用头插法的思想在头上插入

代码

public class SimpleLinkList {

  public static void main(String[] args) {
    Node node1 = new Node(1, "first");
    Node node2 = new Node(2, "second");
    Node node3 = new Node(3, "third");

    LinkList list = new LinkList();
    list.addByNo(node1);
    list.addByNo(node3);
    list.addByNo(node2);

    list.show();

    list.reverse();
    list.show();

    LinkList newHeader = list.reverseByInsert();
    newHeader.show();
  }

}

class LinkList {

  public Node header = new Node(0, "header");

  public LinkList() {

  }

  public LinkList(Node header) {
    this.header = header;
  }

  // 头插法
  public LinkList reverseByInsert() {
    Node newHeader = new Node(0, "header");
    Node current = header.next;
    Node temp;
    while (current != null) {
      temp = current.next;
      current.next = newHeader.next;
      newHeader.next = current;
      current = temp;
    }
    return new LinkList(newHeader);
  }

  // 就地翻转
  public Node reverse() {
    Node current = header.next;
    Node temp = current.next;
    while (temp != null) {
      current.next = temp.next;
      temp.next = header.next;
      header.next = temp;
      temp = current.next;
    }
    return header;
  }

  ;

  public void addNode(Node node) {
    Node temp = header;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp.setNext(node);
  }

  public void addByNo(Node node) {
    Node temp = header;
    while (temp.next != null && temp.next.no < node.no) {
      temp = temp.next;
    }

    node.setNext(temp.next);
    temp.setNext(node);
  }

  public void show() {
    Node temp = header;
    while (temp.next != null) {
      temp = temp.next;
      System.out.println(temp);
    }
  }
}

class Node {

  public int no;
  private String name;
  public Node next;

  public Node(int no, String name) {
    this.no = no;
    this.name = name;
  }

  public void setNext(Node next) {
    this.next = next;
  }

  @Override
  public String toString() {
    return "Node{" +
        "no=" + no +
        ", name='" + name + '\'' +
        '}';
  }
}