编程导航会员会员
登录/注册

左神算法新手班课程学习笔记04


#算法#



//++++++++++++++++++++++++++++++++++++++++++++++


04 链表相关的简单面试题

内容：

单双链表的定义


每个node中除了存在其value，还包括后面node的地址（前后两个node的地址）

单链表：值，一条next指针

双链表：值，一条next指针，一条last指针

链表的难度不在于算法，而在于边界条件非常容易出错。


栈、队列

双端队列

题目：

反转单链表


//提供头节点，反转单链表，返回反转后的头节点
  public static Node reverseLinkedList(Node head){
      Node pre = null;
      Node next = null;
      while(head != null){
          //next的指针指向head节点后一个节点，保存地址防丢失
          next = head.next;
          //将头节点的指针先指向pre
          head.next = pre;
          //pre来到head的位置
          pre = head;
          //head往后走一步
          head = next;
      }
      return pre;
  }



反转双链表


//提供头节点，反转双链表，返回反转后的头节点
public static DoubleNode reverseDoubleList(DoubleNode head){
   DoubleNode pre = null;
   DoubleNode next = null;
   while(head != null){
       //防止丢失后面的节点，用next保护起来
       next = head.next;
       //head的next指向前面节点pre
       head.next = pre;
       //由于是双链表，还要考虑其last指针指向next
       head.last = next;
       //pre的位置向后移动一位
       pre = head;
       //处理好当前节点了，解决下一个节点
       head = next;
  }
   return pre;
}



用单链表实现队列


public static class MyQueue<V>{
   private Node<V> head;
   private Node<V> tail;
   private int size;
   
   //初始化
   public MyQueue(){
       head = null;
       tail = null;
       size = 0;
  }
   //判空函数
   public boolean isEmpty(){
       return size  == 0;
  }
   //查询队列大小函数
   public int size(){
       return size;
  }
   //---------------------------------
   //接受新元素
   public void offer(V value){
       //建立新节点
       Node<V> cur = new Node<V>(value);
       //如果尾节点位空，意味着队列为空
       if(tail == null){
           head = cur;
           tail = cur;
      }else{
           //如果队列不空，先把尾节点的后指针指向新元素，然后把尾节点指向新元素
           tail.next = cur;
           tail.cur;
      }
       size++;
  }
   //---------------------------------
   //弹出元素
   public V poll(){
       v ans = null;
       //如果头节点不为null，意味着队列非空
       if(head != null){
           //把头节点的值保存至ans中
           ans = head.value;
           //头节点后移一位
           head = head.next;
           //元素数量减一
           size--;
      }
       //如果元素全部出队列，必须将tail也指向null,否则最后一个出队列的元素会有tail指针指向，jvm不会将其作为垃圾回收，成为脏数据
       if(head == null){
           tail = null;
      }
       return ans;
  }
   //---------------------------------
   //只返回队列的头元素，不弹出
   public V peek(){
       V ans = null;
       if(head != null){
           ans = head.next;
      }
       return ans;
  }
}



用单链表实现栈


public static class MyStack<V> {
    private Node<V> head;
    private int size;
   
    public MyStack(){
        head = null;
        size = 0;
    }
   
    public  boolean isEmpty(){
        return size == 0;
    }
   
    public int size(){
        return size;
    }
   
    public void push(V value){
        Node<V> cur = new Node<>(value);
        if(head == null){
            head = cur;
        }else{
            cur.next  = head;
            head = cur;
        }
    }
   
    public  V pop(){
        V ans = null;
        if(head != null){
            ans = head.value;
            head = head.next;
            size--;
        }
        return ans;
    }
   
    public V peek(){
        return head != null ? head.value : null;
    }
}



用双链表实现双端队列


public  static class MyDeque<V> {
   private Node<V> head;
   private Node<V> tail;
   private int size;
   
   public MyDeque(){
       head = null;
       tail = null;
       size = 0;
  }
   
   public  boolean isEmpty(){
        return size == 0;
    }
   
   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.last = cur;
           head = cur;
      }
       size++;
  }
   public V pollHead(){
       V ans = null;
       if(head == null){
           return ans;
      }
       size--;
       ans = head.value;
       //只有一个元素
       if(head == tail){
           head = null;
           tail = null
      }else{
           head = head.next;
           head.last = null;
      }
       return ans;  
  }
   
   public V pollTail(){
       V ans = null;
       if(head == null){
           return ans;
      }
       size--;
       ans = tail.value;
       if(head == tail){
           head = null;
           tail = null;
      }else{
           tail = tail.last;
           tail.next = null;
      }
       return ans;
  }
   
     
}



K个节点的组内逆序调整问题：


给定一个单链表的头节点head，和一个正数k实现k个节点的小组内部逆序，如果最后一组不够k个就不调整例子: 调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，k = 3调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8

//得到单链表的第K个节点
public static ListNode GetKGroupEnd(ListNode start, int k){
   while(--k != 0 && start != null){
       start = start.next;
  }
   return start;
}
//根据头节点head和第k个节点，对其范围内进行组内逆序调整
public static void reverse(ListNode start, ListNode end){
   //end先往后走一位
   end = end.next;
   ListNode pre = null;
   ListNode cur = start;
   ListNode next = null;
   //如果现在还没有遍历到end元素处，此时end元素是原end元素位置往后一位，目的是将其指针再往回指。
   //开始逆序操作
   if(cur != end){
       next = cur.next;
       cur.next = pre;
       pre = cur;
       cur = next;
  }
   逆序后的链表的尾节点的指针指向end.
   start.next = end；
}
//主逻辑如下
public static ListNode reverseKGroup(ListNode head,int k){
   ListNode start = head;
   ListNode end = getKGroupEnd(start,k);
   //如果不够K个就不调整，直接返回头节点
   if(end == null){
       return head;
  }
   //第一组凑齐了
   //逆序后head就是原先的end,保持head不动，组内各个元素逆序后直接返回head即可。
   head = end;
   reverse(start,end);
   //lastEnd 上一组的结尾节点
   ListNode lastEnd = start;
   while(lastEnd.next != null){
       start = lastEnd.next;
       //再次数够K个
       end = getKGroupEnd(start.k);
       if(end == null){
           return head;
      }
       reverse(start,end);
       //上一组的结尾节点再次改变为第二组的尾节点
       lastEnd.next = end;
       lastEnd = start;
  }
   //正好是K的整数倍，才会跑到这里
   return head;
   
}
​



两个链表相加问题


给定两个链表的头节点head1和head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表例子 4 -> 3 -> 6 2 -> 5 -> 3返回 6 -> 8 -> 9解释 634 + 352 = 986

//先找长短链表，把长的重定位
​
//求链表的长度
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 ? head1 : head2;
   listNode s = l ==head1 ? head2 : head1;
   //不生成新链表
   ListNode curL = l;
   ListNode curS = s;
   ListNode last = curL;
   int carry  = 0; //进位标志
   int curNum  = 0;
   //第一步，遍历到的长短链表都有元素
   while(curS != null){
       curNum  = curL.val + curS.val + carry;
       //相加的值需要对10取余数
       curL.val = (curNum % 10);
       //进位标志需要除10
       carry = (curNum / 10);
       //把当前的值保存在last中
       last = curL;
       //长短链表继续向后遍历
       curL = curL.next;
       curS = curS.next;
  }
 
   //第二步，遍历到只有长链表上存在元素
   while(curL != null){
       curNum = curL.val + carry;
       cur.val = (curNum % 10);
       carry = (curNum / 10);
       last = curL;
       curL = curL.next;
  }
   //第三步，长链表也结束了
   if(carry != 0){
       //进位标志不为零，在链表尾部加一个值为1的元素。
       last.next = new ListNode(1)；
  }
   return l;
}
​
​



两个有序链表的合并


给定两个有序链表的头节点head1和head2，返回合并之后的大链表，要求依然有序例子 1 -> 3 -> 3 -> 5 -> 7 2 -> 2 -> 3 -> 3-> 7返回 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7

public static ListNode mergeTwoList(ListNode head1, ListNode head2){
    if(head1 == null || head2 = null){
        return head1 = null ? head2 : head1;
    }
    //谁的头节点小，谁的头节点做合并后的大链表的头
    ListNode head = head.val <= head2.val ? head1 : head2;
    ListNode cur1 = head.next;
    ListNode cur2 = head == head1 ? head2 : head1;
    ListNode pre = head;
   
    while(cur1 != null && cur2 != null){
        if(cur1.val <= cur2.val){
            //pre的next指针指向较小的元素
            pre.next = cur1;
            //cur1向后遍历
            cur1 = cur1.next;
        }else{
            //pre的next指针指向较小的元素
            pre.next = cur2;
            //cur2向后遍历
            cur2 = cur2.next;
        }
        //pre 向下一个位置
        pre = pre.next;
    }
    //pre的next指针指向非空的那个元素
    pre.next = cur1 != null ? cur1 :cur2;
    return head;
}


算法
笔记
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
纳西妲首席爹粉
纳西妲首席爹粉
等级
内容推荐
更多
AI编程 技术研究报告 聚焦中国市场：工具生态、技术原理与工作流变革
2
7 种智能体（Agent）设计模式深度解析
17
第一天学习
0
数据库事务基础
2
智能协同云图库-进入编辑报错解决
4
作者分享
更多
【学习笔记】《数据库设计那些事 - 慕课课程》
32
#自我介绍# 各位好，我21年毕业于一所末流211学校的计算机相关专业（焊板子那种）。毕业后在老师的工作室跟着老师做一些应付双创比赛的demo网站,所以算是有一些简单的开发经验，但不多。跟着老师屁股后边混了一年后，就跑路回家复习准备考研。考完研当天就感觉凉透了，所以加入了鱼皮哥的星球。希望通过跟着鱼皮哥做星球项目来提升自己匮乏的项目经验，然后背背八股准备今年的社招。
4
CODE REVIEW中的几个提示 via 陈皓
4
源码学习心得 via 《Java并发编程之美》
7
左神算法新手班课程学习笔记07
11
下载 APP