算法与数据结构之链表

链表的定义，相信大家都知道，这里就不赘述了只是链表分单向链表和双向链表，废话不多说，直接上代码

链表节点的定义：

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

打印链表的两种方式：

    //从前往后打印链表private void print(Node head) {while (head != null) {System.err.print(head.val);head = head.next;}System.err.println();}//从后往前打印链表private void print1(Node head) {while (head != null) {System.err.print(head.val);head = head.pre;}System.err.println();}

翻转单向链表：核心思路是先断开连接，再将next指向前继节点，为了避免断开之后，找不到前继节点，需要用一个临时变量记录前继节点，在下一轮循环的时候把当前节点的next指向上一轮循环时的pre

    //翻转单链表private Node reverList(Node head) {Node pre = null;Node next = null;while (head != null) {//下一次进来的时候连上前一个节点，先记录下前一个节点，不能先断开了后面的节点，不然就找不到了next = head.next;head.next = pre;pre = head;head = next;}return pre;}@Testpublic void reverList() {Node one = new Node(2, new Node(3, new Node(4)));print(one);print(reverList(one));}

翻转双向链表：思路同单向链表一样，只是多了一些判断

   //翻转双向链表private Node reverseDoubleList(Node head) {Node next = null;Node pre = null;while (head != null) {next = head.next;head.next = pre;head.pre = next;pre = head;head = next;}return pre;}@Testpublic void reverseDoubleList() {Node one = new Node(1);Node two = new Node(2);Node three = new Node(3);one.next = two;one.pre = null;two.next = three;two.pre = one;three.pre = two;three.next = null;print(one);print1(three);Node node = reverseDoubleList(one);print(node);print1(one);}

从链表中删除指定的数据：

 //从单链表中删除指定的数据private Node removeList(Node head, int target) {Node pre = null;Node next = null;while (head != null) {//第一轮循环找到新的头结点，因为要删除的数据可能是第一个也可能是最后一个next = head.next;if (target != head.val) {break;}head = next;}next = pre = head;//while (next != null) {if (target == next.val) {next = next.next;pre.next = next;//相等的时候提前把pre和下一个连起来，这样下一个如果相等，只需要移动pre即可continue;}pre = next;//不相等的时候pre记录前一个节点，等到下一轮如果相等时候就可以把pre和next连上了next = next.next;}return head;}@Testpublic void removeList() {Node one = new Node(2, new Node(5, new Node(2, new Node(3, new Node(2)))));print(one);print(removeList(one, 2));}