链表结构基础

单链表

节点结构

常见单链表节点结构，也可实现成泛型。

public class Node {
  public int value;
  public Node next;

  public Node(int data) {
    value = data;
  }
}

反转单链表

public Node reverseLinkedList(Node head) {
  Node pre = null;
  Node next = null;
  while (head != null) {
    next = head.next;
    head.next = pre;
    pre = head;
    head = next;
  }
  return pre;
}

删除给定的值

public Node removeValue(Node head, int num) {
  while (head != null) {
    if (head.value != num) {
      break;
    }
    head = head.next;
  }
  Node pre = head;
  Node cur = head;
  while (cur != null) {
    if (cur.value == num) {
      pre.next = cur.next;
    } else {
      pre = cur;
    }
    cur = cur.next;
  }
  return head;
}

双链表

双链表节点结构

常见双链表节点结构，也可实现成泛型。

public class DoubleNode {
  public int value;
  public DoubleNode last;
  public DoubleNode next;

  public DoubleNode(int data) {
    value = data;
  }
}

反转双链表

public DoubleNode reverseDoubleList(DoubleNode head) {
  DoubleNode pre = null;
  DoubleNode next = null;
  while (head != null) {
    next = head.next;
    head.next = pre;
    head.last = next;
    pre = head;
    head = next;
  }
  return pre;
}

删除给定的值

public DoubleNode removeValue(DoubleNode head, int num) {
  while (head != null) {
    if (head.value != num) {
      break;
    }
    head = head.next;
  }
  DoubleNode pre = head;
  DoubleNode cur = head;
  while (cur != null) {
    if (cur.value == num) {
      pre.next = cur.next;
      cur.next.last = pre;
    } else {
      pre = cur;
    }
    cur = cur.next;
  }
  return head;
}