title:链表 author:xiongxinwei
第12节 链表
❤️ 算法学习笔记和LeetCode的刷题笔记与记录。Myblog:http://nsddd.top
[TOC]
单链表和双链表经典反转
对于单链表来说，除了最后一个结点，每个结点都有指向一个结点。而反转，则是把所有的链表进行转过来，头结点指向空~
headExample 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Example 2:
Input: head = [1,2]
Output: [2,1]Example 3:
Input: head = []
Output: []Go解题
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode //定义一个链表
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev //改变链表
prev = curr //
curr = next
}
return prev
}java解题
/**
* 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 reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head; //cur = null;
while(cur != null){
ListNode tmp = cur.next; //保存下一个结点
cur.next = pre; //指向前一个结点
pre = cur; //保存后续的结点
cur = tmp; //当前结点是之前保存的哪个结点
}
return pre;
}
}双链表的反转
- 记住当前的环境（后面的环境）
- 调整
class Solution {
//链表结构
public static class DoubleNode {
public int value;
public DoubleNode last; //上一个结点
public DoubleNode next; //下一个结点
}
public ListNode reverseList(ListNode head) {
DoubleNode pre = null;
DoubleNode next = null; //cur = null;
while(head != null){
next = head.next; //next指向下一个结点
head.next = pre; //指向前一个结点
head.last = next; //保存后续的结点
pre = head;
head = next; //当前结点是之前保存的哪个结点
}
return pre;
}
}用单链表实现队列和栈
要求每一个操作都是O(1)单链表是没办法实现双端队列的，因为单链表没有办法跳出上一个，所以使用的是双链表.
class Solution {
//链表结构
public static class MyDeque {
public int value;
public MyDeque head; //头
public MyDeque tail; //尾
}
public int size() {
return size;
}
//头部加
public void pushHead(V value) {
Node<V> cur = new Node<>(value); // 新插入的结点
if(head == null) { //如果原来的头结点是空的话，直接指向它
head = cur;
tail = cur;
}else{
cur.next = head; //新结点的下一个结点head
head.last = cur; //head的前一个结点指向cur
head = cur;
}
size++;
}
//尾巴加入
public void pushTail(V value) {
Node<V> cur = new Node<>(value); // 新插入的结点
if(head == null) { //如果原来的头结点是空的话，直接指向它
head = cur;
tail = cur;
}else{
tail.next = cur; //尾巴的下一个节点指向cur
cur.last = tail; //cur的前一个结点指向cur
tail = cur;
}
size++;
}
//头部删除
public V pollHead() {
V ans = null;
if(head == null) { //如果原来的头结点是空的话，直接指向它
return ans
}
size -- //说明有删除
ans = head.value;
if(head == tail) {
//只有一个结点
tail = null;
head = null;
}else{
head = head.next;
head.last = null; //不能忘掉，不然内存泄露
}
// 尾部删除
public V pollTail() {
V ans = null;
if(head == null) { //如果原来的头结点是空的话，直接指向它
return ans
}
size -- //说明有删除
ans = head.value;
if(head == tail) {
//只有一个结点
tail = null;
head = null;
}else{
tail = tail.next; //最后一个结点指向前一个
tail.next = null; //释放
}
}k个结点的组内逆序调整
JavaGo给定一个单链表，实现一个调整单链表的函数，使得每 K 个节点之间的值逆序，如果最后不够 K 个节点一组，则不调整最后几个节点。
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]一般链表题目考察的时候细节
环境
// *
// * 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; }
// * }划分边界处理以及返回最后面的一个数
public static ListNode getKGroupEnd(ListNode start, int k) {
while(--k != 0 && start != null) {
//k = 5 k = 0 end start = 123456 , return 5 而且不够k返回null
start = start.next;
}
return start;
}反转，改变头尾指针指向
public static void reverse(ListNode start, ListNode end) {
//之前的分区最后一个结点，s前一个结点不用关心,也看不到，指向null就行
end = end.next;
ListNode pre = null;
ListNode cur = start;
ListNode next = null; //cur当前来到start位置
while(cur != end) { //没到最后面，需要走到最后的时候往回指向，和上面单链表反转操作一样
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = end; //原来头结点连接原来尾结点 --> next
}串起来
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(start,k); //数到k的点返回给end
if(end == null) {
//没凑齐，直接返回
return head;
}
head = end; //凑齐了，就把最后面的给头,头不变
reverse(start,end); //反转
ListNode lastEnd = start; //上一组的结尾结点
while(lastEnd.next != null) {
start = lasEnd.next; //新结点
end = getKGroupEnd(start,k); //最后一个结点调整
if(end == null) {
return head;
}
reverse(start,end);
lastEnd.next = end;
lastEnd = start;
}
return head; //正好是整数倍
}链表中的两数相加
输入：
[7,2,4,3]
[5,6,4]输出：
[2,9,8,3]思路
不额外生成链表，在长链表上面进行修改
- 三个阶段：
- 只有长链表
- 只有一个链表
- 都没有
- 第一阶段：当前的数值等于链表1 + 链表2 + 进位
- 第二阶段：当前的数值等于链表L+进位
- 第三阶段：当前的数值等于
进位 - 有进位就加一个链表
- 没有进位~
lastListNode last = curLnull /**
* 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 addTwoNumbers(ListNode l1, ListNode l2) {
int len1 = listLength(l1);
int len2 = listLength(l2);
ListNode l = len1 >= len2 ? l1 : l2; //长的链表
ListNode s = l == l1 ? l2 : l1; //短的链表
ListNode curL = l; //长链表当前结点
ListNode curS = s; //短链表当前结点
ListNode last = curL; //last长链表,设置跟踪结点
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;
}
public static int listLength(ListNode head) {
//求链表长度
int len = 0;
while(head != null) {
len++;
head = head.next;
}
return len;
}
}原题改版
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]代码
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<Integer>();
Deque<Integer> stack2 = new ArrayDeque<Integer>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int a = stack1.isEmpty() ? 0 : stack1.pop();
int b = stack2.isEmpty() ? 0 : stack2.pop();
int cur = a + b + carry;
carry = cur / 10;
cur %= 10;
ListNode curnode = new ListNode(cur);
curnode.next = ans;
ans = curnode;
}
return ans;
}
}合并两个链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4谁作为主结点，我们选取第一个值进行判断
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head1 = l1;
ListNode head2 = l2;
if(head1 == null || head2 == null) {
return head1 == null ? head2:head1;
}
ListNode head = head1.val <= head2.val ? head1 : head2;
ListNode cur1 = head.next; //小头第一个结点为cur1
// ! 注意：这里的head一直都不动，而且pre一直指向的是head
ListNode cur2 = head == head2 ? head1 : head2;
ListNode pre = head;
while(cur1 != null && cur2 != null) {
//链表都不为空
if(cur1.val < cur2.val) {
pre.next = cur1;
cur1 = cur1.next;
}else{
pre.next = cur2;
cur2 = cur2.next;
}
pre = pre.next;
}
//直到有一个链表是空的
if(cur2 != null) {
pre.next = cur2; //不用遍历直接结束
}else{
pre.next = cur1;
}
return head;
}
}ListNode pre = head;因为head和pre指向的是同一个区域 – 注意，不是说head指向的是pre,因为pre往后移动的时候head还是指向那个区域的位置没有动过。
*head = *pre指向的是同一片区域，可以给个临时的赋值变量
ListNode x = pre;
return x; //结果一样