一、单向链表
1、单向链表节点结构(可以实现成泛型)
public class Node{public int value;public Node next;public Node(int data) {value = data;}
}
2、双向链表节点结构
public class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}
}
二、单向链表和双向链表最简单的练习题
1、链表相关的问题几乎都是coding问题
(1)单链表和双链表如何反转
package class02;/*** 单链表和双链表的反转*/
public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {value = data;}}public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}}public static Node reverseLinkedList(Node head) {Node pre = null;Node next = null;// 核心是交换pre和next指针while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}public static 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;}}
单链表示意图:
(2)把给定值都删除
2 -> 0 -> 3 -> 4 -> 3 -> 7 -> null
删除3,返回
2 -> 0 -> 4 -> 7 -> null
package class02;/*** 把给定值都删除*/
public class Code02_DeleteGivenValue {public static class Node {public int value;public Node next;public Node(int data) {value = data;}}public static Node removeValue(Node head, int num) {// 先看头部要删多少// 遍历链表找到第一个不是num值的节点while (head != null) {if (head.value != num) {break;}head = head.next;}// head来到第一个不需要删的位置// 后面用cur来遍历,head你就别动了Node pre = head;Node cur = head;while (cur != null) {if (cur.value == num) {pre.next = cur.next; // 跳过值为num的节点} else {pre = cur;}cur = cur.next;}return head;}
}