链表
单链表
定义
-
把存储数据元素的信息的域称为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素$a_0$的存储映像，称为节点(Node).
-
n个节点链结成一个链表，即为线性表($a_1$,$a_2$,$a_3$,....,$a_n$)的链式存储结构，因为此链表的每个结点只包含一个指针域，所以叫做单链表。
结构
public class Node{
public int value; //声明一个变量存储数据
public Node next; //声明一个变量存储后续的节点位置
public Node(int data){
value = data;
}
}
反转单链表:
思路
- 声明两个指针，分别是pre指针和next指针
- 对当前指针元素进行遍历，通过判断它的指针域是否为空，判断是否完成循环遍历
- pre指针记录上一轮节点的位置，next指针记录当前指针下一个节点的位置，这样，cur指针就可以把节点域指向上一个节点，然后通过next指针，把当前cur指针指向下一个节点。
- 从而完成单链表的反转
public static 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 class DoubleNode{
public int value;
public DoubleNode last; //上一个节点位置
public DoubleNode next; //下一个节点位置
public DoubleNode(int data){
value = data;
}
}
反转双链表：
思路:
- 和单链表思路非常像，只是多了一步把当前节点的last指针指向下一个节点
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;
}
相关算法题
K个一组反转列表：
题目：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
链表结构
public static class ListNode {
public int value;
public ListNode next;
}
思路：
- 首先声明两个方法
- 第一个方法完成返回该节点的往后的n个节点，目的是为了得到要反转的节点范围的最后一个节点
public static ListNode getKGroupEnd(ListNode start,int k){
while(k != 1 && start != null){
start = start.next;
k--;
}
return start;
}
2. 第二个方法反转开始节点start和结束节点end，并在完全反转后，将反转前的开始节点start指向结束节点end的下一个节点
public static void reverse(ListNode start,ListNode end){
end = end.next;
ListNode pre = null;
ListNode cur = start;
ListNode next = null;
while(cur != end){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = end;
}
-
先判断当前给出的链表长度是否满足k个节点，不满足直接返回
满足的话，首先将头节点指向第一组的末尾节点，因为链表反转后，头节点必定是第一组的k节点
反转第一组的start和end节点,然后声明一个指针lastNode，指向上一组的start节点
-
随后，通过lastNode.next指针，得到下一组将要翻转链表的头节点，然后通过getKGroupEnd方法，获得当前翻转组的尾节点，再将这组的头节点和尾节点做一个翻转，并将上一组翻转节点的lastNode节点的next指向这组的尾节点
-
对4这个过程进行一个循环，直到当前最后一组链表长度正好满足k个节点，或者最后一组链表长度小于k个节点，都返回开始的head节点
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(start,k);
if(end == null){
return head;
}
//凑齐第一组
head = end;//将头节点指向第一个要反转的end节点
reverse(start,end);
//上一组的结尾节点
ListNode lastNode = start;
while(lastEnd.next != null){
start = lastNode.next;
end = getKGroupEnd(start,k);
if(end == null){
return head;
}
reverse(start,end);
lastNode.next = end;
lastNode = start;
}
return head;
}
两数相加：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
链表结构：
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
思路：
- 逆序顺序存储两个非负整数，拿各自链表上对应节点的值相加，得到的sum值，对10取余，则是当前的位数的值，对10取整，1，则要进一位，0，则不进
- 短链表循环完，判断进位值是否有1，有1则加上，没有，则直接取长链表的节点值
- 如果两个链表一样长，需要判断进位值是否有1，有的话，生成一个新节点，值为1，放在要返回的链表的最后
public static int listLength(ListNode head){
int len = 0;
while(head != null){
len++;
head = head.next;
}
return len;
}
public static ListNode addTwoNumbers(ListNode head1,ListNode head2){
int len1 = listLength(head1);
int len2 = listLength(head2);
ListNode l = len1 > len2 ? len1 : len2;
ListNode s = len1 > len2 ? len2 : len1;
ListNode curL = l;
ListNode curS = s;
ListNode last = curL;
int carry = 0;
int curNum = 0;
while(curS != null){
curNum = curL.val + curS.val + carry;
curL.val = curNum % 10;
carry = curNum / 10;
last = curL;
curL = curL.next;
curS = curS.next;
}
while (curL != null) {
curNum = curL.val + carry;
curL.val = curNum % 10;
carry = curNum / 10;
last = curL;
curL = curL.next;
}
if(carry != 0){
last.next = new ListNode(1);
}
return l;
}
合并两个有序列表：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
1. 声明两个指针cur1，cur2分别指向两个有序列表的头节点
2. 声明一个头节点指针，指向cur1和cur2两个有序列表里最小的头节点，最后作为该方法的返回节点
3. 对cur1和cur2的值作比较，谁小，添加谁的当前节点，并将添加的当前节点往下移一位，然后声明一个pre指针保存上个操作节点的位置。
4. 做循环，直到某一个链表节点全部添加完，然后添加剩余链表的节点
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if(head1 == null && head2 == null){
return head1 == null ? head2: head1;
}
ListNode head = head1.val < head2.val ? head1 : head2;
ListNode cur1 = head.next;
ListNode cur2 = head1.val < head.val ? head2 : head1;
ListNode pre =head;
while(cur1 != null && cur2 != null){
if(cur1.val <= cur2.val){
pre.next = cur1;
cur1 = cur1.next;
} else {
pre.next = cur2;
cur.next = cur2;
}
pre = pre.next;
}
pre.next = cur1 != null ? cur1 : cur2;
return head;
}
删除指定值
思路：
1. 当前头节点进行搜索，直到当前头节点指向非指定值的节点
2. 声明一个cur指针指向当前节点，一个pre指针指向上一轮节点，当前节点值等于指定值，略过这一节点，使上一个节点直接指向下一个节点
3. 返回头节点
public class Node{
public int val;
public Node next;
public Node(int data){
this.val = data;
}
}
public Node remove(Node head,int num){
/*
if(head == null){
return head;
}
*/
while(head.next != null){
if(head.val != num){
break;
}
head = head.next;
}
// 1.head == null
//2 .head != null
Node pre = head;
Node cur = head;
while(cur != null){
if(cur.val == num){
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
返回链表的中点
通用节点：
public class Node{
public int value;
public Node next;
public Node(int v){
this.value = v;
}
}
题目一：
输入链表头节点，奇数长度返回中点，偶数长度返回上中点
注：比如1->2->3->4链表，上中点为2，下中点为3。
思路：
-
弄两个指针slow和fast，一个步长为1，一个步长为2，两个同时从第一个点出发
- 如果该链表总长是奇数，则两个指针要走的路程必定是偶数,则slow直接停在该路程的中上点，再加上起点node，所以slow就停在了mid
- 例子：总长是9，则经过路程是8，mid是4。
- 1 -> 2 -> 3 -> 4 -> 5 - > 6 -> 7 -> 8 -> 9,则1+4=5
- 用数组存储该链表，则数组长度是9的话，是$[0,1,2,3,4,5,6,7,8]$,直接(arr.length - 1)/2，就能得到中点位置
- 如果该链表总长是偶数，则两个指针要走的路程必然奇数，fast指针会停在len-1节点的位置，slow会停在(len-1)长度(奇数)的中点位置上一个位置，设路程的mid节点左边节点个数x,右边节点个数x，则slow节点的左右边个数都满足$x-1 = x +1$，再加上起点节点，x = x +1，表明slow右边节点比左边节点多1个，说明slow在中上点位置
- 例子：总长是8，则经过路程是7，mid是4。
- 1 -> 2 -> 3 -> 4 -> 5 - > 6 -> 7 -> 8 ,则1+3=4
- 用数组存储该链表，则数组长度是8的话，是$[0,1,2,3,4,5,6,7]$,直接(arr.length - 1)/2，就能得到中上点位置
public static midOrUpMidNode(Node head){ if(head == null || head.next == null || head.next.next==null){ return head; } Node slow = head.next; Node fast = head.next.next; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } public staic void comparator1(Node head){ if(head == null || head.next == null || head.next.next==null){ return head; } int len = 0; Node cur = head; while(cur !=null){ len++; cur = cur.next; } Node[] nodeArr = new Node[len]; cur = head; for(int i = 0;i<nodeArr.length;i++){ nodeArr[i] = cur; cur = cur.next; } return nodeArr[(len - 1)/2]; }
- 如果该链表总长是奇数，则两个指针要走的路程必定是偶数,则slow直接停在该路程的中上点，再加上起点node，所以slow就停在了mid
题目二：
输入链表头节点，奇数长度返回中点，偶数长度返回下中点
思路：
- 偶数个数返回下中点，说明fast指针需要多跳一次，又因为fast不能设在头节点之前，就和slow同时放在head.next之后
- 奇数个数返回中点，原本fast指针正好跳到终点，加上一个节点，fast指针跳的回合不变
public static void midOrDownMidNode(Node head){
if(head == null || head.next == null || head.next.next==null){
return head;
}
Node slow = head.next;
Node fast = head.next;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public staic void comparator2(Node head){
if(head == null || head.next == null || head.next.next==null){
return head;
}
int len = 0;
Node cur = head;
while(cur !=null){
len++;
cur = cur.next;
}
Node[] nodeArr = new Node[len];
cur = head;
for(int i = 0;i<nodeArr.length;i++){
nodeArr[i] = cur;
cur = cur.next;
}
return nodeArr[len/2];
}
题目三
输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
思路：
- 相比于题目一：slow直接少跳一回合即可
public static void midOrDownMidNode(Node head){
if(head == null || head.next == null || head.next.next==null){
return null;
}
Node slow = head;
Node fast = head.next.next;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public staic void comparator2(Node head){
if(head == null || head.next == null || head.next.next==null){
return head;
}
int len = 0;
Node cur = head;
while(cur !=null){
len++;
cur = cur.next;
}
Node[] nodeArr = new Node[len];
cur = head;
for(int i = 0;i<nodeArr.length;i++){
nodeArr[i] = cur;
cur = cur.next;
}
return nodeArr[(len-3)/2];
}
题目四：
输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
思路：
1. 相比于题目二：slow直接少跳一回合即可
public static void midOrDownMidNode(Node head){
if(head == null || head.next == null || head.next.next==null){
return null;
}
Node slow = head;
Node fast = head.next;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public staic void comparator2(Node head){
if(head == null || head.next == null || head.next.next==null){
return head;
}
int len = 0;
Node cur = head;
while(cur !=null){
len++;
cur = cur.next;
}
Node[] nodeArr = new Node[len];
cur = head;
for(int i = 0;i<nodeArr.length;i++){
nodeArr[i] = cur;
cur = cur.next;
}
return nodeArr[(len-2)/2];
}
请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list
思路：
- 用栈后进先出的特点，对每个节点入栈，然后拿栈头和开始元素做对比，全部一样，返回true
- 改变链表结构，用快慢指针，使slow指针指在中点位置，或者上中点位置，然后slow后的链表翻转节点，slow.next为空，然后从头开始遍历链表，和fast指针一起对比，直到cur指针为null
public class Code02_IsPalindromeList {
public static class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public static boolean isPalindrome1(ListNode head){
if( head == null || head.next == null){
return true;
}
ListNode cur = head;
Stack<ListNode> stack = new stack<>();
while(cur != null){
stack.push(cur);
cur=cur.next;
}
cur = head;
while(cur != null){
if(cur.val != stack.pop().val){
return false;
}
cur = cur.next;
}
return true;
}
//栈存左边一半
public static boolean isPalindrombyL(ListNode head){
if(head == null || head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head;
Stack<ListNode> stack = new stack<>();
while(fast.next != null fast.next.next != null){
stack.add(slow);
slow = slow.next;
fast = fast.next.next;
}
if(fast.next != null){
stack.add(slow);
}
slow = slow.next;
while(!stack.isEmpty()){
if(slow.val != stack.pop().val){
return false;
}
slow = slow.next;
}
rturn true;
}
}
//栈存右边一半
public static boolean isPalindrombyR(ListNode head){
if(head == null || head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
Stack<ListNode> stack = new Stack<>();
slow = slow.next;
while(slow != null){
stack.add(slow);
slow = slow.next;
}
while(!stack.isEmpty()){
if(head.val != stack.pop().val){
return false;
}
head = head.next;
}
return true;
}
//解法二
//翻转链表
public static void reverListNode(ListNode head){
if(head == null || head.next == null){
return;
}
ListNode cur = head;
ListNode pre = null;
ListNode next = null;
while(cur!=null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public static boolean isPalindrom3(ListNode head){
if(head == null || head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
fast = reverListNode(slow);
while(head != null){
if(head.val != fast.val){
return false;
}
head = head.next;
fast = fast.next;
}
return true;
}
复制带随机链表的指针
https://leetcode.cn/problems/copy-list-with-random-pointer/
思路：
- 用hashMap存储每个指针节点，和对应的复制节点。然后循环遍历给每个复制结点的random赋值
- 再每个初始节点的后面加上一个复制节点，然后根据每个初始节点的random找到对应复制节点。最后，在复原两个链表
public class Node{
int val;
Node next;
Node random;
public Node(int val){
this.val = val;
this.next = null;
this.random = null;
}
}
public Node dpCopyNodeWithOutPointer(Node node){
Node ans = new Node(node.val);
return ans;
}
public Node copyRandomList1(Node head){
if(head == null){
return head;
}
Node cur = head;
Node tmp = null;
HashMap<Node,Node> nodeMap = new HashMap<>();
while(cur != null){
tmp = dpCopyNodeWithOutPointer(cur);
nodeMap.put(cur,tmp);
cur=cur.next;
}
cur = head;
while(cur !=null){
tmp = nodeMap.get(cur);
tmp.next = nodeMap.get(cur.next);
tmp.random = nodeMap.get(cur.random);
cur = cur.next;
}
return nodeMap.get(head);
}
public Node copyRandomList2(Node head){
if(head == null){
return head;
}
Node cur = head;
Node tmp = null;
Node next = null;
while(cur != null){
next = cur.next;
tmp = dpCopyNodeWithOutPointer(cur);
cur.next = tmp;
tmp.next = next;
cur = next;
}
cur = head;
while(cur != null){
tmp = cur.next;
tmp.random = cur.random.next;
cur = cur.next.next;
}
Node ans = head.next;
n1 = head;
n2 = head.next;
while(cur != null){
next = n1.next.next;
n1.next = next;
n2.next = next != null ? next.next:null;
n1 = next;
n2 = n1 != null ? n1.next : null;
}
return ans;
}