算法总结一: Linked List的高频操作-爱代码爱编程
学习目标:
算法总结一: Linked List
学习内容:
1、 Leetcode题库Linked List tag高频题学习时间:
1、 周一至周天晚上 7 点—晚上9点学习产出:
1、 技术笔记 1 篇2、解题思路视频1个
=====================================
linked list的特性包含:无法直接获取一个list的size,无法random access。一些基本操作如:
reverse,
findMid,
reorder,
sort,
remove,
merge,
partition
易错点较多。以下为学习总结:
1.Reverse
206. Reverse Linked List
recursion的解法:
好奇:子问题中如果当前head是2,那么head.next=null会执行吗?
解答:跑idea时会的,每一步都会执行
nxt.next=head;
head.next=null;
但由于是从尾巴开始递归/back track的,
所以前一步的head.next=null都会被改写,
最后一步是null才定局,最终接地。
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
//1-> [2->3->4->5->NULL]
//head nxt
ListNode nxt=head.next;
ListNode newHead=reverseList(head.next);
//子问题是head.next
//这里也相当于head=head.next往下走。
nxt.next=head;
head.next=null;
return newHead;
}
}
iteration的解法:
class Solution {
public ListNode reverseList(ListNode head) {
// 1----2----3----null
//prev cur nxt
// prev cur
ListNode prev=null;
ListNode cur=head;
while(cur!=null){
ListNode nxt=cur.next;
cur.next=prev;//反指针
prev=cur; //走一步
cur=nxt; //走一步
}
return prev;
}
}
25. Reverse Nodes in k-Group
recursion的解法:
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(k<=1) return head;
//1.count k,ex: k=3
int count=0;
ListNode cur=head;
while(count<k && cur!=null){ //count==3跳出
cur=cur.next;
count++;
}
if(count==k){
ListNode reversedHead = reverseLL(head,k);
//2.reverse k nodes
//3.recursively solve this problem: .next=reverseKGroup(head+k, k)
head.next=reverseKGroup(cur, k);
//1.next=reverseKGroup(4,3); 指向新头,所以这里总的要返回新头
return reversedHead;
}
//否则,无法做count和reverse,就:
return head;
}
public ListNode reverseLL(ListNode head,int k){
ListNode prev=null;
ListNode cur=head;
while(k>0){
ListNode nxt=cur.next;
cur.next=prev;//null<--1 改变指向,
prev=cur;//prev指针往右边走
cur=nxt;//cur指针往右边走,
k--;
}
return prev;
}
}
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m == 1) {
// You can also expand the code here to get rid of the helper function 'reverseN'
return reverseN(head, n);
}
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
ListNode successor = null;
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
successor = head.next;
return head;
}
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return last;
}
}
2.Find middle
876. Middle of the Linked List
Given a non-empty, singly linked list with head node head, return a middle node of linked list.
If there are two middle nodes, return the second middle node.
class Solution {
public ListNode middleNode(ListNode head) {
ListNode s=head;
ListNode f=head;
//1--2--3--4--5
// s f
//1--2--3--4--5--6
// s
// f
//这题希望返回第二个,4,是mid,所以s和f还需要走一步,
//所以条件是(f!=null && f.next!=null){
while(f!=null && f.next!=null){
s=s.next;
f=f.next.next;
}
return s;
}
}
如果是普通的情况,12345,123456都返回3,那么条件为:
while(f.next!=null && f.next.next!=null){
这里决定了mid,断开前也可以拿到mid.next作为第二段的头。这在sort,reorder或判断isPalindrome中也有应用。
public ListNode middleNode(ListNode head) {
ListNode s=head;
ListNode f=head;
//1--2--3--4--5
// s f
//1--2--3--4--5--6
// s
// f
while(f.next!=null && f.next.next!=null){
s=s.next;
f=f.next.next;
}
return s;
}
用快慢双指针的方式,延伸一下,还可以用来判断list是否有环。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode slow=head;
ListNode fast=head;
// 1--2--3--4--5
// s
// f
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}
}
接下来,对findMid以及reverse的应用,又延伸到了多个重构linked list的操作中:
class Solution {
public void reorderList(ListNode head) {
if (head == null) return;
ListNode slow=findMid(head);
ListNode s=reverse(slow);
ListNode first = head, second = s;
while (second.next != null) {
ListNode tmp = first.next; //tmp这里是一颗垫脚石,每次承接住,当前断开的first,
first.next=second;
first=tmp;
tmp=second.next;///tmp这里是一颗垫脚石,每次承接住,当前断开的second,
second.next=first;
second=tmp;
}
}
ListNode findMid(ListNode head){
if(head==null) return head;
ListNode s=head,f=head;
while(f!=null && f.next!=null){
s=s.next;
f=f.next.next;
}
return s;
}
ListNode reverse(ListNode head){
if(head==null || head.next==null) return head;
ListNode nxt=head.next;
ListNode newHead=reverse(head.next);
nxt.next=head;
head.next=null;
return newHead;
}
}
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode end = getMid(head);
ListNode mid=end.next;
end.next=null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
cur.next=list1;
list1=list1.next;
cur=cur.next;
}else{
cur.next=list2;
list2=list2.next;
cur=cur.next;
}
}
cur.next=(list1!=null)?list1:list2;
return dummy.next;
}
ListNode getMid(ListNode head) {
if(head==null || head.next==null) return head;
ListNode s=head,f=head;
while(f.next!=null && f.next.next!=null){
s=s.next;
f=f.next.next;
}
return s;
}
}
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null) return true;
ListNode mid=findMid(head);
ListNode secondHead=reverse(mid.next);
while(secondHead!=null){
if(head.val!=secondHead.val){
return false;
}
head=head.next;
secondHead=secondHead.next;
}
return true;
}
public ListNode reverse(ListNode head){
if(head==null || head.next==null) return head;
ListNode nxt=head.next;
ListNode newHead=reverse(head.next);
nxt.next=head;
head.next=null;
return newHead;
}
public ListNode findMid(ListNode head){
ListNode s=head,f=head;
while(f.next!=null && f.next.next!=null){
s=s.next;
f=f.next.next;
}
return s;
}
}
3.Remove
203. Remove Linked List Elements
class Solution {
public ListNode removeElements(ListNode head, int val) {
// [1,2,6,3,4,5,6]
// p c
// h
//d
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode prev=dummy;
ListNode cur=head;
while (cur != null) {
if(cur.val==val){
prev.next=cur.next;
cur=cur.next;
}else{
prev=prev.next;
cur=cur.next;
}
}
return dummy.next;
}
}
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null) return head;
ListNode cur=head;
while(cur.next!=null){
//[1,2,3, 3, 3]
// c next
if(cur.val==cur.next.val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
return head;
}
}
82. Remove Duplicates from Sorted List II
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// 1--1--1--2--3
// s-------h--n
// 1--2--3--3--4--4--4--5
// s h n
if(head==null || head.next==null) return head;
ListNode dummy=new ListNode(0,head);
ListNode s=dummy;
while(head!=null){
if(head.next!=null && head.val==head.next.val){
while(head.next!=null && head.val==head.next.val){
head=head.next;//跳过所有相同
}
s.next=head.next;//2接上5
}else{
s=s.next;//s从2跳到5
}
head=head.next;
}
return dummy.next;
}
}
4. Merge
21. Merge Two Sorted Lists
solution1: recursively
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
//子问题:
if(l1.val<l2.val){//就可以确定当前是l1
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
solution2: iteratively
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
cur.next=l1;
cur=cur.next;
l1=l1.next;
}else{
cur.next=l2;
cur=cur.next;
l2=l2.next;
}
}
//post process
if(l1!=null){
cur.next=l1;
}
if(l2!=null){
cur.next=l2;
}
return dummy.next;
}
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null) return null;
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
PriorityQueue<ListNode> minHeap=new PriorityQueue<>(new Comparator<ListNode>(){
@Override
public int compare(ListNode l1,ListNode l2){
// if(l1.val==l2.val) return 0;
return l1.val<l2.val?-1:1;
}
});
for(ListNode l:lists){
if(l!=null) //bug1
minHeap.offer(l);
}
while(!minHeap.isEmpty()){
ListNode curNode=minHeap.poll();
cur.next=curNode;
cur=cur.next;
if(curNode.next!=null)//bug2
minHeap.offer(curNode.next);
}
return dummy.next;
}
}
5. Partition
86. Partition List
class Solution {
public ListNode partition(ListNode head, int x) {
//10:10
ListNode smallDummy=new ListNode(0);
ListNode smallH=smallDummy;
ListNode largeDummy=new ListNode(0);
ListNode largeH=largeDummy;
ListNode dummy=new ListNode(0);
dummy.next=head;
while(head!=null){
if(head.val<x){
smallH.next=head;
smallH=smallH.next;
}else{
largeH.next=head;
largeH=largeH.next;
}
head=head.next;
}
smallH.next=largeDummy.next;
largeH.next=null;
return smallDummy.next;
}
}
6. 其它
其它一些有趣的操作:
19. Remove Nth Node From End of List
这题需要删除从尾巴开始数的第n个node,但是尾巴没有指针。
题中要求one pass,即不能数一遍list再操作。
就先派出一个first先走n步,走到第n个,然后second也开始同步走,这样维持一个n的差距。如下图:
n=3
1 2 3 4 5
f
s
f先走到3,然后和s一起开始走,f走到5停下,s走到2。此时维持3个node的距离。那么s的下一个node就是要删除的目标。s.next=s.next.next;
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
重点:
1.不能丢掉对头的控制权。如果头有可能会改变,因此不确定头是谁,使用dummy node是个很好的选择,在增、删、reorder之后返回dummy.next作为新头。
2.可能修改/断开的地方,时刻注意是否能找得到某个node,如果可能丢失,就用一个指针mark住。比如:
ListNode tmp = first.next;
first.next=second;
first=tmp;
tmp是垫脚石,每次承接住first的下一个,first指向second ,断开的first还能找到tmp,移动到tmp。
3.理解recursion在linked list中的应用。如何将大的问题,分解成小一号的问题,在最小单元上完成一个重复性操作,这个操作逐步recurse,完成整个问题。
Thank you for reading !
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/weixin_43879909/article/details/111096955