• 算法通关村第二关——链表反转白银挑战笔记

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

    文章目录

    前言

    本篇文章主要研究了链表反转的几个问题

    一、指定区间链表反转

    leetcode92:给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
    在这里插入图片描述

    示例1：
    输入：head = [1,2,3,4,5], left = 2, right = 4
    输出：[1,4,3,2,5]
    示例 2：
    输入：head = [5], left = 1, right = 1
    输出：[5]

    在上一篇文章中《算法通关村第二关——链表反转青铜挑战笔记》我们已经提到反转链表主要两种方法，一种是借助虚拟头节点的头插法和不借助虚拟头节点的穿针引线法。

    1.1 头插法

    由于是在指定区间进行链表反转，使用头插法，我们需要得到两个条件，一个是确定虚拟头节点的位置，一个是反转区间的长度。确定玩这两个基本的条件，代码就很简单啦！

    代码如下

     ListNode newnode=new ListNode(-1,head);
        ListNode pre=newnode;
        int left_temp=left;
        while(pre!=null){
        //经常喜欢直接用left--，导致下面再用left的时候还以为是原来的值
            if(--left_temp==0){
                break;
            }
            pre=pre.next;
        }
        /*也可以用循环直接找到pre，这样就不怕啦
		*for(int i=0;i
        
        ListNode cur =pre.next;
        for(int i=0;i<right-left;i++){
            ListNode next =cur.next;
            cur.next=next.next;
            next.next=pre.next;
            pre.next=next;
        }
        return newnode.next;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    1.2 穿针引线法

    使用穿针引线法，需要把反转的链表单独摘出来进行翻转。这样就把原链表分割成三分：反转区间前面的链表，反转区间的链表，反转区间后面的链表。在反转区间的链表反转完成后，在将该链表拼接回去，我们得到四个节点，反转区间左边节点的前驱pre_left,反转区间左边节点leftnode，反转区间右边节点rightnode，反转区间右边节点的后继right_next。

    代码如下

     public ListNode reverseBetween(ListNode head, int left, int right) {
      ListNode newnode=new ListNode(-1,head);
      ListNode pre_left=newnode,leftnode,rightnode,right_next;
      //寻找反转区间左边节点的前驱pre_left,反转区间左边节点leftnode
      for(int i=0;i<left-1;i++){
        pre_left=pre_left.next;
      }
      leftnode=pre_left.next;
      //寻找反转区间右边节点rightnode，反转区间右边节点的后继right_next
      rightnode=leftnode;
      for(int i=0;i<right-left;i++){
          rightnode=rightnode.next;
      }
      right_next=rightnode.next;
      //要把反转区间最后一个置空，否则就会导致反转区间后面的链表全部被反转
      rightnode.next=null;
      //进行区间反转，并对反转后的三块链表进行拼接
      pre_left.next= fanzhuan(leftnode);
      leftnode.next=right_next;
      return newnode.next;

    }
    public ListNode fanzhuan(ListNode head){
    //使用穿针引线法进行链表反转
        ListNode pre=null,cur=head;
        while(cur!=null){
            ListNode next =cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    二、两两交换链表中的节点

    Leetcode24：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

    在这里插入图片描述

    示例1
    输入：head = [1,2,3,4]
    输出：[2,1,4,3]

       public ListNode swapPairs(ListNode head) {
        ListNode newnode=new ListNode(-1,head);
       ListNode temp=newnode;
        while(temp.next!=null&&temp.next.next!=null){
            ListNode l1=temp.next;
            ListNode l2=temp.next.next;
            l1.next=l2.next;
            l2.next=temp.next;
            temp.next=l2;
            temp=l1;
        }
        return newnode.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    三、 链表加法

    leetcode445：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

    你可以假设除了数字 0 之外，这两个数字都不会以零开头。


    在这里插入图片描述

    输入：l1 = [7,2,4,3], l2 = [5,6,4]
    输出：[7,8,0,7]

    将链表反转，对位相加，并要考虑进位，最后再将链表反转

     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            l1=fanzhuan(l1);
            l2=fanzhuan(l2);
            ListNode newnode =new ListNode(-1,null);
            int i=0;
            ListNode temp=newnode;
            while(l1!=null&&l2!=null){
                int val =(l1.val+l2.val+i)%10;
                i=(l1.val+l2.val+i)>=10?1:0;
                temp.next=new ListNode(val);
                l1=l1.next;l2=l2.next;
                temp=temp.next;
            }
            if(l1==null){
                while(l2!=null){
                    int val=(l2.val+i)%10;
                    i=(l2.val+i)>=10?1:0;
                    temp.next=new ListNode(val);
                    l2=l2.next;
                    temp=temp.next;
                }
            }
            if(l2==null){
                while(l1!=null){
                    int val=(l1.val+i)%10;
                    i=(l1.val+i)>=10?1:0;
                    temp.next=new ListNode(val);
                    l1=l1.next;
                    temp=temp.next;
                }
            }
            if(i==1){
                temp.next=new ListNode(1);
            }
            return fanzhuan1(newnode.next);

    }
    //体验不同的反转方法
    public ListNode fanzhuan (ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead=fanzhuan(head.next);
        head.next.next=head;
        head.next=null;
        return newhead;
    }
    public ListNode fanzhuan1(ListNode head){
        ListNode newnode =new ListNode(-1,null);
        ListNode temp=head;
        while(temp!=null){
            ListNode next = temp.next;
            temp.next = newnode.next;
            newnode.next=temp;
            temp=next;
        }
        return newnode.next;
    }
    public ListNode fanzhuan2(ListNode head){
        ListNode pre=null,cur=head,next;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    四、 链表回文序列在思考

    leetcode234:给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。


    在这里插入图片描述

    示例
    输入：head = [1,2,2,1]
    输出：true

    使用快慢指针找到中点，并使用慢指针直接将前半部分进行链表反转

    public boolean isPalindrome(ListNode head) {
        ListNode fast=head,slow=head;
        ListNode cur=null,pre=null;
        while(fast!=null&&fast.next!=null){
            cur=slow;
            slow=slow.next;
            fast=fast.next.next;
            cur.next=pre;
            pre=cur;
        }
        if(fast!=null){
            slow=slow.next;
        }
        while(pre!=null){
            if(pre.val!=slow.val){
                return false;
            }
            pre=pre.next;
            slow=slow.next;
        }
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    总结

    主要记录了链表反转的一些拓展应用题目

  • 相关阅读:
    AQS源码三视-JUC系列
    基于多尺度卷积神经网络特征融合的植株叶片检测技术
    广告学概论笔记
    金仓数据库KingbaseES数据库管理员指南--18数据库作业调度
    第一章 教育基础（04 教师专业发展）
    Redis的哨兵机制,一文全解
    Java中类的方法重载和方法重写
    小程序中的分页查询
    Springboot整合shiro
    采购货物和服务的有效步骤
  • 原文地址：https://blog.csdn.net/qwquu/article/details/132611010