我要评论
目录
链表常用技巧
1. 画图. -> 更加直观和形象.
2. 引入虚拟头结点.
- 更便于处理边界情况.
- 更方便对于链表的操作.
3. 快慢双指针.
- 判环
- 找链表中环的入口
- 找链表中倒数第n个结点
链表中常用操作
1. 头插. -> 逆序链表
2. 尾插.
两数相加
题目描述
题解
解法：模拟两数相加过程即可.
两个链表都是逆序存储数字的，即两个链表的个位数、⼗位数等都已经对应，可以直接相加。（如果不是逆序链表，那就需要手动逆序了） 在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进 位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再 new ⼀个结点储存最⾼位。
代码实现
public listnode addtwonumbers(listnode l1, listnode l2) {
listnode cur1 = l1, cur2 = l2; //指向两个链表的头节点
listnode newhead = new listnode(0); //虚拟头节点
listnode prev = newhead; //进行尾插操作的指针
int ret = 0; //表示进位
while(cur1 != null || cur2 != null || ret != 0) {
if(cur1 != null) {
ret += cur1.val;
cur1 = cur1.next;
}
if(cur2 != null) {
ret += cur2.val;
cur2 = cur2.next;
}
prev.next = new listnode(ret % 10);
prev = prev.next;
ret /= 10;
}
return newhead.next;
}两两交换链表中的节点
题目描述
题解
解法一: 模拟. -> 画图
解法二：递归.
- 递归函数的含义：交给你⼀个链表，将这个链表两两交换⼀下，然后返回交换后的头结点；
- 函数体：先去处理⼀下第⼆个结点往后的链表，然后再把当前的两个结点交换⼀下，连接上后⾯处理后的链表；
- 递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤交换，直接返回。
代码实现
public listnode swappairs(listnode head) {
if(head == null || head.next == null) {
return head;
}
listnode newhead = new listnode(0); // 虚拟头节点
listnode prev = newhead;
listnode cur = head;
listnode next = cur.next;
listnode nnext = next.next;
//模拟循环过程
while(cur != null && next != null) {
//交换节点
cur.next = nnext;
next.next = cur;
prev.next = next;
//修改指针
prev = cur;
cur = nnext;
if(cur != null) {
next = cur.next;
}
if(next != null)
nnext = next.next;
}
return newhead.next;
}递归代码：
public listnode swappairs(listnode head) {
if(head == null || head.next == null) {
return head;
}
listnode tmp = swappairs(head.next.next);
listnode cur = head.next;
cur.next = head;
head.next = tmp;
return cur;
}重排链表
题目描述
题解
算法思路：
- 找中间节点；
- 中间部分往后的逆序；
- 合并两个链表
代码实现
public void reorderlist(listnode head) {
// 特殊情况
if(head == null || head.next == null || head.next.next == null) {
return ;
}
listnode fast = head;
listnode slow = head;
// 1.找中间节点
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 2.后面部分逆序(头插法)
listnode newhead = new listnode(0);
listnode cur = slow.next;
slow.next = null; //分割两个链表
while(cur != null) {
listnode curnext = cur.next;
cur.next = newhead.next;
newhead.next = cur;
cur = curnext;
}
// 3.合并两个链表
listnode cur1 = head, cur2 = newhead.next;
listnode head2 = new listnode(0);
listnode prev = head2;
while(cur1 != null) {
prev.next = cur1;
prev = prev.next;
cur1 = cur1.next;
if(cur2 != null) {
prev.next = cur2;
prev = prev.next;
cur2 = cur2.next;
}
}
}合并 k 个升序链表
题目描述
题解
解法一： 利用优先级队列做优化.
把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次
k
个链表中，最⼩的元素是哪
个。
代码实现
public listnode mergeklists(listnode[] lists) {
//1.创建一个小根堆
priorityqueue<listnode> heap = new priorityqueue<>((head1,head2) -> head1.val - head2.val);
//2.将所有的头结点放到小根堆中
for(listnode head : lists) {
if(head != null) {
heap.offer(head);
}
}
//3. 合并链表
listnode newhead = new listnode(0);
listnode cur = newhead;
while(!heap.isempty()) {
listnode tmp = heap.poll();
cur.next = tmp;
cur = tmp;
//把tmp的下一个节点放到小根堆中
if(tmp.next != null) {
heap.offer(tmp.next);
}
}
return newhead.next;
}
发表评论