算法与数据结构之链表
链表的定义,相信大家都知道,这里就不赘述了只是链表分单向链表和双向链表,废话不多说,直接上代码
链表节点的定义:
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();}
翻转单向链表:
//翻转单链表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));}