力扣链表刷题总结(简单)

简介: 力扣链表刷题总结(简单)

力扣链表刷题总结(简单)


链表:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。


对于链表相关的题通常可以通过迭代、转换为数组、单指针、快慢指针等方法去做。通常为了节省时间或空间复杂度,会优先考虑快慢指针进行解题,置于其他时候具体问题需要具体分析。


关于链表的一些小技巧:

  • 当需要产生一个新链表时,不妨设置含有虚拟节点的链表来存储新链表,可避免出现空指针异常
  • 当需要删除某个节点的时,不妨定位到待删除节点的上一个节点,next 指针,使其指向待删除节点的下一个节点,即可完成删除操作
  • 当需要找到第K个节点时,不妨考虑快慢指针,快指针走K步,慢指针走N-k步,当快指针为空时,慢指针的位置即为我们所求
  • 当需要寻找某个位置时,不妨快慢指针多走几遍,相当于第一遍确定位置,第二遍寻值

注:对于其他问题,要具体问题具体分析,不是所有链表问题都适合采用以上技巧。刷算法题时,要多动脑子,不能形成思维定式,从题目中,一点点抽取关键问题。

吾日三省吾身:

  • 付出不亚于任何人的努力
  • 自立,自省,自爱,自强
  • 谦虚低调,不卑不亢,常怀感恩之心

以下列举综合性较强的题解:

//合并两个升序链表
/**
*思路:链表相关的问题多可用快慢指针的解法,设置两个指针分别指向两个链表,依次比较大小
*本题亮点:当产生一个新链表时,就创建一个dummy【虚拟头结点】,可避免出现空指针异常。
*/
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //首先建立一个新的链表,用于存储合并后的链表
        ListNode dummy = new ListNode(-1); //此处空间置为-1就是为了占位
        ListNode p = dummy;
        //将list两个链表分别存储在p1,p2中
        ListNode p1 = list1,p2 = list2;
       //当两个链表均不为0时,方可以进行排序
        while(p1 != null && p2 != null){
        if(p1.val> p2.val){
            p.next = p2;
            p2 = p2.next;
        }else{
            p.next = p1;
            p1 = p1.next;
        }
        p = p.next;
        }
        //当两个链表分别为空时,则直接返回另一个链表即可
      if(p1 == null){
        p.next = p2;
      }
      if(p2==null){
          p.next = p1;
      }
      return dummy.next;
    }
}
//删除链表的第N个节点
/**
 *思路:因为删除后会产生一个新链表,所以直接定义含一个虚拟节点的新链表。
 *      要删除第N个节点,只需要让(N-1)的下一个指针指向下一个地址即可
 *      因为定义了虚拟节点,所以此处为n.next = n.next.next;
 * 亮点:本题需要先找到倒数第N个节点。 再使用 n.next = n.next.next; 
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
      //定义虚拟节点链表
      ListNode dummy = new ListNode(-1);
      dummy.next = head;

      //删除倒数第N个,要先找到倒数第N-1个
     ListNode x = Findfrom(dummy,n+1);
        x.next = x.next.next;
        return dummy.next;
    }
      //此处参考找链表中倒数第N个节点
      //先去找第N个节点
    public ListNode Findfrom(ListNode head,int k){
        //先定义一个指针
    ListNode p1 =head;

        //先遍历一次链表,找出N的位置
      for(int i= 0 ; i < k; i++){
         p1 = p1.next;
     }

      //再定义一个指针,此时p1 和 p2正好相差了N-K 步
     ListNode p2 = head;
     //当p1为空,即指向链表的末尾是,p2的位置就是所需节点的位置
     while(p1 != null){
      p2 = p2.next;
      p1 = p1.next;
  }
  return p2;
     
    }
}
//环形链表
/**
 * 思路:判断链表中是否含环,通常采用的是快慢指针的做法。
 *   重点:先判定链表为空否,再判断快慢指针相等否 
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
    //首先定义快慢指针
    ListNode fast = head,slow =head;
    //判断给定链表是否为空链表,若为空,直接返回false
     if (head == null || head.next == null){
            return false;
        }
     //若链表不为空,则判断快指针是否为空
        while(fast != null && fast.next != null){
        //不为空,则慢指针走一步,快指针走两步
            slow = slow.next;
            fast = fast.next.next;
          //当二者相等时,则代表存在环路
            if(slow == fast){
                return true;
            }
        } 
        return false;
    }
}
//相交链表
/**
 * 思路:根据题目可以得出如果两个链表相交,那么相交点之后的长度是相同的
 * 同样建立两个指针,分别指向两个链表,并且从头结点位置开始,消除两个链表的长度差 即可
 * 让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。    
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果链表为空则无相交节点
    if (headA == null || headB == null) return null;
       //建立两个指向链表头指针的节点
    ListNode pA = headA, pB = headB;
    //等指针A.B不相等时,则证明无相交节点,继续遍历
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
        
    }
}
相关文章
|
22天前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
16天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
16天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
16天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
12 1
|
5天前
|
存储 算法 C语言
刷题训练之链表
刷题训练之链表
10 0
|
16天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
10 0
|
22天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
22天前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
22天前
|
算法
【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素
|
22天前
|
存储 算法 C语言
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
【数据结构与算法 刷题系列】环形链表的约瑟夫问题

热门文章

最新文章