链表及常见操作

相对于数组使用连续的内存空间来存储，链表不需要连续的存储空间，而是使用“指针”将零散的内存块串联起来；链表结点除了要存储数据外，还要记录下一个结点的地址。

链表最常见的结构有单链表，双链表和循环链表；

​

​

​

​单链表只有一个方向，结点只需要一个额外的空间指向后面的结点，只能从前往后进行遍历查找数据；而双向链表可以向前和向后查找数据，相对比较灵活，但是双向链表需要额外的两个空间来存储后继结点和前驱结点的地址；存储同样多的数据，双向链表需要比单链表占用更多的空间。

链表常见操作（Java实现）

1.单链表类

 static class Node {
  int data;
  Node next;
  public Node(int data, Node next) {
    this.data = data;
    this.next = next;
  }
  @Override
  public String toString() {
    //省略具体方法实现
  }
}  

2.单链表反转

 private Node reversal(Node head){
  if(head == null || head.next == null)
    return head;

  Node newHead = null;
  Node nextNode = null;
  while (head != null){
    nextNode = head.next;
    head.next = newHead;
    newHead = head;
    head = nextNode;
  }
  return newHead;
}  

3.单链表反转（递归实现）

 private Node reversal2(Node head){
  if(head == null || head.next == null)
    return head;
  Node temp = head.next;
  Node newHead = reversal2(temp);
  temp.next = head;
  head.next = null;
  return newHead;
}  

4.链表中环的检测

 private boolean checkCircle(Node head){
  if(head == null || head.next == null)
    return false;
  //一个快指针，一个慢指针，如果存在环，则快指针一定会追上慢指针
  Node fast = head;
  Node slow = head;
  while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast)
      return true;
  }
  return false;
}  

5.两个有序链表合并（递归）

 private Node mergeNode(Node head1, Node head2) {
  if(head1 == null || head2 == null)
    return head1 == null ? head2 : head1;
  Node newNode;
  if (head1.data > head2.data) {
    newNode = head2;
    newNode.next = mergeNode(head1, head2.next);
  } else {
    newNode = head1;
    newNode.next = mergeNode(head1.next, head2);
  }
  return newNode;
}  

6.删除链表倒数第 n 个结点

 private Node deleteNode(Node head, int n) {
  if(head == null || head.next == null)
    return null;
  //前后指针，前指针先走n步，当前指针到达最后结点时，后指针刚好在待删除结点处
  Node first = head;
  Node second = head;
  for (; n > 0; n--) {
    first = first.next;
  }
  while (first.next != null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return head;
}