代码编织梦想

学习目标:

算法总结一: 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;
    }
}

92. Reverse Linked List II

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是否有环。

141. Linked List Cycle

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的操作中:

143. Reorder 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;
    }
}

148. Sort List

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;
    }
}

234. Palindrome Linked List

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;
    }

23. Merge k Sorted Lists

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 !
Alt

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/weixin_43879909/article/details/111096955

左神算法基础班 第1章 第一周学习——认识复杂度和简单排序算法-爱代码爱编程

左神算法课基础班 1. 复杂度、对数器、二分法、位运算与异或运算 1.1 排序 1.1.1 Java自带的排序函数 Arrays.sort(arr); 1.1.2 冒泡排序   时间复杂度O(n*n),空间复杂度O(1)1.1.3 选择排序   时间复杂度O(n*n),空间复杂度O(1)保留数组中最小or最大的值的下标1.1.4 插入排序 

Java锁机制总结-爱代码爱编程

1. 什么是线程安全问题? 多线程操作公共对象时,如何保证对象数据不变脏。 2. synchronized和ReentrantLock锁的区别? synchronized,在写法上变现为原生语法级别,是非公平锁,可重入锁,java 1.6版本前性能较差, reentranLock, 也是可重入锁,写法上变现为API级别的锁,相对synchroniz

jsp、servlet、jdbc实现留言板(可记住密码)-爱代码爱编程

文章目录 一、目标二、JDBC使用说明三、代码总结 使用工具:mysql、IDEA 一、目标 对留言板进行优化: 登陆页面输入用户名、密码,提交给某个servlet,该servlet可以检索数据库,验证用户名和密码是否合法,给出验证结果二、JDBC使用说明 JDBC基本功能 建立连接、发送SQL语句,处理数据库操作结果 mysql

JDBC常用方法封装-爱代码爱编程

常用方法封装 学过JDBC后,会时常会用增删改查的方法,而一而再,再而三的重复的写会使代码出现冗余并且不太美观,因此将会需要使用的方法封装起来则成了上上之选,所以,我决定将会需要用到的方法进行封装,使用起来也会方便很多. 1.可以将JDBC中最常用的三个步骤进行封装: 加载驱动 获取连接 获取执行sql语句的对象 执行 处理结果 关闭资源

牛牛与字符串2-爱代码爱编程

原题链接 题目描述 , 牛牛拿到了一个字符串。他想知道除去字符串本身以外,这个字符串最大的公共前后缀的长度是多少? **例如,**对于字符串ABABA而言,“ABA”即是它的前缀,也是它的后缀,且是最长的公共前后缀,因此最大的长度是3。 , 牛牛无法解决该问题,所以他只好向你求助,给定一个只包含大写字母的字符串s,返回除去字符串本身以外公共前后缀最大长

The matching wildcard is strict, but no declaration can be found for element ‘rabbit:queue‘.-爱代码爱编程

web项目启动时xml解析错误,具体错误信息如下: Offending resource: URL [jar:file:/usr/local/tomcat/webapps/ROOT/WEB-INF/lib/****-config-3.0.3-SNAPSHOT.jar!/spring-com/applicationContext-appcontext.xm

左神算法基础班 第1章 第一周学习——认识复杂度和简单排序算法-爱代码爱编程

左神算法课基础班 1. 复杂度、对数器、二分法、位运算与异或运算 1.1 排序 1.1.1 Java自带的排序函数 Arrays.sort(arr); 1.1.2 冒泡排序   时间复杂度O(n*n),空间复杂度O(1)1.1.3 选择排序   时间复杂度O(n*n),空间复杂度O(1)保留数组中最小or最大的值的下标1.1.4 插入排序 

[MATLAB]Jacobi迭代-爱代码爱编程

[MATLAB代码]关于使用雅可比迭代法求线性方程组的数值解 jacobi.m %定义Jacobi迭代函数 function [x, n] = jacobi(A, b, x0, eps) %计算迭代矩阵 D = diag(diag(A)); L = -tril(A,-1); U = -triu(A,1); BJ = D\(L+U); f = D\b; %

LeetCode:实现摇摆序列-爱代码爱编程

A sequence of number is called a wiggle sequence if the differeces between successive numbers strictly alternative between positive and negative.The frist differece(if one exists

LeetCode 100. 相同的树 做题小结-爱代码爱编程

题目: 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: tr

原地堆排序(不占用额外空间)(C++实现)-爱代码爱编程

原地堆排序,不占用额外空间 // 原地堆排序,不占用额外空间 template<typename T> void shiftDown(T data[], int n, int i) { using uint = unsigned int; uint k = i; whil

leetcode 滑动窗口小结 (一)-爱代码爱编程

目录 小结以及代码框架76. 最小覆盖子串滑动窗口代码以及注释567. 字符串的排列滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串化简框架reference 小结以及代码框架 滑动窗口技巧属于双指针技巧。 该算法的思路为维护一个窗口,不断滑动,然后更新答案。 大致框架如下:[参考labuladong的