数据结构-链表及相关算法
// 单链表节点的结构
public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}
链表
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含data 域，next域:指向下一个节点.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定.
基础知识
哈希表的简单介绍
- 哈希表在使用层面上可以理解为一种集合结构
- 如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet)
- 如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMap)
- 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
- 使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为
O(1)，但是常数时间比较大 - 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
- 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地
址的大小
在java中 HashSet就是一个只使用HashMap的key的一个集合。
有序表的简单介绍
- 有序表在使用层面上可以理解为一种集合结构
- 如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)
- 如果既有key，又有伴随数据value，可以使用TreeMap结构(C++中叫OrderedMap)
- 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
- 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
- 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现
不同 - 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
- 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占
用是这个东西内存地址的大小 - 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复
杂度
有序表的固定操作：
- void put(K key, V value)：将一个（key，value）记录加入到表中，或者将key的记录
更新成value。 - V get(K key)：根据给定的key，查询value并返回。
- void remove(K key)：移除key的记录。
- boolean containsKey(K key)：询问是否有关于key的记录。
- K firstKey()：返回所有键值的排序结果中，最左（最小）的那个。
- K lastKey()：返回所有键值的排序结果中，最右（最大）的那个。
- K floorKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，
key的前一个。 - K ceilingKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个。
以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录数
练习
反转单链表和双链表
节点结构：
public class TreeNode {public int num;public TreeNode next;public TreeNode last;public TreeNode(int num) {this.num = num;}public TreeNode() {}
}
public class Node {public int num;public Node next;public Node(int num, Node next) {this.num = num;this.next = next;}
}
两种方式反转链表结构：
/*** 反转单向链表* while循环*/public static Node reversal1(Node head) {Node last = head.next;head.next = null;while (last != null) {Node temp = last.next;last.next = head;head = last;last = temp;}return head;}/*** 反转单链表* 递归* @param head* @return*/public static Node reversal2(Node head) {if(head.next == null) {return head;}Node last = reversal2(head.next);head.next.next = head;head.next = null;return last;}/*** 反转双向链表* 循环* @param head* @return*/public static TreeNode reversal3(TreeNode head) {TreeNode next = head.next;head.next = null;while (next != null) {head.last = next;TreeNode temp = next.next;next.next = head;head = next;next = temp;}return head;}/*** 反转双向链表* 递归* @param head* @return*/public static TreeNode reversal4(TreeNode head) {if (head.next == null) {return head;}TreeNode node = reversal4(head.next);head.next.last = head.next.next;head.next.next = head;head.next = null;return node;}打印两个有序链表的公共部分
public static void portion(Node n1, Node n2) {while(n1 != null && n2 != null) {if (n1.num == n2.num) {System.out.print(n1.num);n1 = n1.next;n2 = n2.next;}else if (n1.num < n2.num) {n1 = n1.next;}else if (n1.num > n2.num) {n2 = n2.next;}}}
技巧
面试时链表解题的方法论
- 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
- 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧：
- 额外数据结构记录（哈希表等）
- 快慢指针
示例
判断回文链表
/*** 不使用额外的空间，适用于面试* @param head* @return*/public static boolean plalindrome2(Node head) {//首先通过快慢指针找到中间的节点，如果是偶数：中间左边，奇数：中间节点Node slowNode = head;Node quickNode = head;while(quickNode.next!= null && quickNode.next.next != null) {slowNode = slowNode.next;quickNode = quickNode.next.next;}//此时慢指针，就到了中间位置，那么在此后面的的节点 指针反转quickNode = slowNode.next;slowNode.next = null;while (quickNode != null) {Node temp = quickNode.next;quickNode.next = slowNode;slowNode = quickNode;quickNode = temp;}while (head.next != null && slowNode.next != null) {if (head.num != slowNode.num) {return false;}head = head.next;slowNode = slowNode.next;}return true;}/*** 使用额外的数据结构，空间复杂度高，适用于笔试* @param head* @return*/public static boolean plalindrome1(Node head) {Stack<Node> stack = new Stack();Node node = head;while (node != null) {stack.add(node);node = node.next;}while (head != null) {if (head.num != stack.pop().num) {return false;}head = head.next;}return true;}将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
/*** 使用有限的变量解答题目* @param node* @param num* @return*/private static Node pivot1(Node node, int num) {Node ssNode = null;Node seNode = null;Node msNode = null;Node meNode = null;Node bsNode = null;Node beNode = null;while (node != null) {if (node.num < num) {if (ssNode != null) {seNode.next = node;seNode = node;}else {ssNode = node;seNode = node;}}else if (node.num > num) {if (bsNode != null) {beNode.next = node;beNode = node;}else {bsNode =node;beNode = node;}}else if (node.num == num){if (msNode != null) {meNode.next = node;meNode = node;}else {msNode = node;meNode = node;}}node = node.next;}if (ssNode == null) {if (meNode == null) {ssNode = bsNode;}else {meNode.next= bsNode;ssNode = msNode;}}else {if (meNode == null) {seNode.next = bsNode;}else {seNode.next = msNode;meNode.next = bsNode;}}return ssNode;}/*** 采用数组 的结构 然后利用快速排序的思路，进行处理* @param node* @param num*/private static void pivot(Node node, int num) {Node[] nodes = new Node[6];int i = 0;while (node != null) {nodes[i++] = node;node = node.next;}System.out.println(Arrays.toString(nodes));int start = 0, end = nodes.length-1;for (int j = 0; j <= end; j++) {if (nodes[j].num < num) {Node temp = nodes[j];nodes[j] = nodes[start];nodes[start] = temp;start++;}else if (nodes[j].num > num) {Node temp = nodes[j];nodes[j] = nodes[end];nodes[end] = temp;j--;end --;}}System.out.println(Arrays.toString(nodes));}复制含有随机指针节点的链表
【题目】一种特殊的单链表节点类描述如下
class Node {
int value;
Node next;
Node rand;
Node(int val) {
value = val;
}
}
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节
点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点
head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度O(N)，额外空间复杂度O(1)
/*** 使用 Map数据结构 * @param head* @return*/public static ListNode copy(ListNode head) {Map<ListNode, ListNode> map = new HashMap<>();ListNode node = head;while (node != null) {map.put(node, new ListNode(node.value));node = node.next;}ListNode hListNode = head;while (head != null) {map.get(head).next = map.get(head.next);map.get(head).rand = map.get(head.rand);head = head.next;}return map.get(hListNode);}/*** 不使用额外空间 * @param head* @return*/public static ListNode copy1(ListNode head) {ListNode node = head;ListNode temp;while (node != null) {temp = node.next;node.next = new ListNode(node.value);node.next.next = temp;node = temp;}node = head;while (node != null) {temp = node.next;if (node.rand == null) {temp.rand = null;}else {temp.rand = node.rand.next;}node = node.next.next;}return head.next;}两个单链表相交的一系列问题
【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实
现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返
回null
【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度
请达到O(1)。
//没做
题
递归反转单链表
public ListNode reverse(ListNode head) {if (head.next == null) {return head;}ListNode lastListNode = reverse(head.next);head.next.next = head;head.next = null;return lastListNode;}
递归反转前n个节点
ListNode successor = null; // 后驱节点// 反转以 head 为起点的 n 个节点，返回新的头结点
public ListNode reverseN(ListNode head, int n) {if (n == 1) { // 记录第 n + 1 个节点successor = head.next;return head;}// 以 head.next 为起点，需要反转前 n - 1 个节点ListNode last = reverseN(head.next, n - 1);head.next.next = head;// 让反转之后的 head 节点和后面的节点连起来head.next = successor;return last;
}
递归反转指定范围的节点
ListNode reverseBetween(ListNode head, int m, int n) {// base caseif (m == 1) {return reverseN(head, n);}// 前进到反转的起点触发 base casehead.next = reverseBetween(head.next, m - 1, n - 1);return head;
}
递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。
https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-shua-lian-biao-ti-mu-xun-lian-di-gui-si-wei/di-gui-fan-zhuan-lian-biao-de-yi-bu-fen
leetcode
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode success1 = null;public ListNode reverseBetween(ListNode head, int left, int right) {if (left == 1) {return reverseBetween(head, right);}head.next = reverseBetween(head.next, --left, --right);return head;}public ListNode reverseBetween(ListNode head, int n) {if (n == 1) {success1 = head.next;return head;}ListNode laListNode = reverseBetween(head.next, --n);head.next.next = head;head.next = success1;return laListNode;}}
k个一组反转链表
我的代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode[] arr = reverse(head, k);ListNode preListNode = arr[2];ListNode preListNode1 = arr[0];while (arr[1] != null) {if (!judge(arr[1], k)) {break;}arr = reverse(arr[1], k);preListNode.next = arr[0];preListNode = arr[2];}return preListNode1;}public boolean judge(ListNode head, int k) {ListNode node = head; while (node != null) {node = node.next;k--;if (k == 0) {return true;}}return false;}public ListNode[] reverse(ListNode head, int k) {ListNode[] arr = new ListNode[3];ListNode preNode = head;ListNode currentNode = head.next;ListNode tempListNode = null;while (currentNode != null&&k>1) {tempListNode = currentNode.next;currentNode.next = preNode;preNode = currentNode;currentNode = tempListNode;if (k == 2) {break;}--k;}head.next = currentNode;arr[0] = preNode;arr[1] = currentNode;arr[2] = head;return arr;}}
拉布拉多
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null) {return null;}ListNode a,b;a = head;b = head;for (int i = 0; i < k; i++) {if (b == null) {return head;}b = b.next;}// 反转前 k 个元素ListNode newHead = reverse(a, b);// 递归反转后续链表并连接起来a.next = reverseKGroup(b, k);return newHead; }public ListNode reverse(ListNode a, ListNode b) {ListNode pre,cur,temp;pre = a;cur = a.next;while (cur != b) {temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}}
回文链表
方式一：
空间复杂度为O(1)的
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ListNode a = head;ListNode b = head;while (b.next != null && b.next.next != null) {b = b.next.next;a = a.next;}ListNode c;c = a.next;a.next = null;while (c != null) {b = c.next;c.next = a;a = c;c = b;}c = a;b = head;while (b != null && a != null) {if (b.val != a.val) {return false;}b = b.next;a = a.next;}//复原return true;}
}
方式二：
使用栈
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {Stack<Integer> stack = new Stack<>();ListNode node = head;while (node != null) {stack.add(node.val);node = node.next;}while (head != null) {if (stack.pop() != head.val) {return false;}head = head.next;}return true;}
}方式三：
使用递归
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {ListNode left;public boolean isPalindrome(ListNode head) {left = head;return traverse(head);}public boolean traverse(ListNode head) {// 前序遍历代码if (head == null) {return true;}// 后序遍历代码boolean res = traverse(head.next);boolean b = res && head.val == left.val;left = left.next;return b;}
}面试题 02.02. 返回倒数第 k 个节点
//双指针
public int kthToLast(ListNode head, int k) {ListNode n1 = head;ListNode n2 = head;while (k != 0) {n1 = n1.next;k--;}while (n1 != null) {n1 = n1.next;n2 = n2.next;}return n2.val;}彩蛋
加入我的知识星球，加入自学编程者的聚集地。