面试热题（反转链表）

淩亂°似流年 2023-10-14 17:39 9阅读 0赞

> 给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ，其中 `left <= right` 。请你反转从位置 `left` 到位置 `right` 的链表节点，返回 **反转后的链表** 。

![ac2d3ecf9fce90c6a23a0fe086a6299f.jpeg][]

链表的题，大部分都可以用指针或者递归可以做，指针如果做不出来的话，建议多声明几个指针就可以做的出来了

方法一：

因为链表中的头结点也有可能进行反转操作，所以我们为了不失一般性，创建一个虚拟头结点进行操作

![3cf4bb17c2e94bd0916035bf1fb4395b.png][]

![58706f1dab7141d2bd58ae09cd6ea7bb.png][]

我们需要旋转\[left,right\]区间内的链表结点，所以我们就必须要知道left的上一个结点是谁，所以我们可以使用快慢指针进行操作，slow慢指针指向我们left的上一个结点,对区间内的节点进行反转，过程如下：

![131167b1781d42ba853902e477247702.png][]

![77114135a8b240d9839caff9dd553d39.png][]

源代码如下：

public ListNode reverseBetween(ListNode head, int left, int right) {
                   //如果头结点为空或者是头结点的后继点为空的话直接返回head
                       if(head==null||head.next==null){
                          return head;
                      }
                      //创建一个虚拟头结点
                      ListNode dummyHead=new ListNode(0);
                      dummyHead.next=head;
                      //设置两个指针
                      ListNode slow=dummyHead;//慢指针-->指向left指针指向节点的上一个节点
                      ListNode fast=dummyHead.next;//快指针  将left指针与right指针中的节点加到left指针前面(包括right指针)
                //进行移动,将slow指针移向left指针的前一个节点
                for (int i = 1; i <left; i++) {
                         slow=slow.next;
                         fast=fast.next
                        ;
               }
               //将left和right指针中的节点移向left节点前(包括right指针对应的节点)
            for (int i = 0; i <right-left; i++) {
                ListNode removeNode=fast.next;
                fast.next=fast.next.next;
                removeNode.next=slow.next;
                slow.next=removeNode;
    
            }
             //返回头结点后的链表长度
            return dummyHead.next;
        }

**方法二：**

在以前学习得到过程中我们已经学过了链表翻转（必会）

//这几行代码必须得会，链表题最多的就是翻转，你可以直接当一个api去用
    public ListNode reverse(ListNode root){
            if(root==null||root.next==null){
                return root;
            }
            //前扑
            ListNode pre=null;
            ListNode cur=root;
            //后继
            ListNode next=null;
            while(cur!=null){
                next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=next;
            }
               //返回的是翻转后的头结点
               return pre;
        }

现在我们只需要找到需要翻转链表区间的前扑后继，然后通过前扑的next指向翻转后的头结点，让反转后的尾结点指向后继，这道题就解出来了

![35fd241220684780a9a7dc653316c8b2.png][]

源代码如下(这种方法比较推荐，比较容易理解)：

public ListNode reverseBetween(ListNode head, int left, int right) {
            if(head==null||left>=right){
                return head;
            }
            //找到left的前驱节点，因为会设计头结点的操作，所以要创建一个虚拟头结点
            ListNode dummyNode=new ListNode(0,head);
            ListNode pre=dummyNode;
            //找到对应的前驱节点
            for (int i =1; i <left; i++) {
               pre=pre.next;
            }
            //未反转链表的头结点
            ListNode leftNode=pre.next;
            ListNode rightNode=leftNode;
            pre.next=null;
            //找到未反转链表的尾结点
            for (int i = 1; i <=right-left; i++) {
                   rightNode=rightNode.next;
            }
            //找到后继
            ListNode end=rightNode.next;
            rightNode.next=null;
            ListNode newStartNode=reverse(leftNode);
            pre.next=newStartNode;
            leftNode.next=end;
            return dummyNode.next;
        }
    
        //反转链表
        public ListNode reverse(ListNode root){
            if(root==null||root.next==null){
                return root;
            }
            ListNode pre=null;
            ListNode cur=root;
            ListNode next=null;
            while(cur!=null){
                next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=next;
            }
               return pre;
        }

[ac2d3ecf9fce90c6a23a0fe086a6299f.jpeg]: https://img-blog.csdnimg.cn/img_convert/ac2d3ecf9fce90c6a23a0fe086a6299f.jpeg
[3cf4bb17c2e94bd0916035bf1fb4395b.png]: https://img-blog.csdnimg.cn/3cf4bb17c2e94bd0916035bf1fb4395b.png
[58706f1dab7141d2bd58ae09cd6ea7bb.png]: https://img-blog.csdnimg.cn/58706f1dab7141d2bd58ae09cd6ea7bb.png
[131167b1781d42ba853902e477247702.png]: https://img-blog.csdnimg.cn/131167b1781d42ba853902e477247702.png
[77114135a8b240d9839caff9dd553d39.png]: https://img-blog.csdnimg.cn/77114135a8b240d9839caff9dd553d39.png
[35fd241220684780a9a7dc653316c8b2.png]: https://img-blog.csdnimg.cn/35fd241220684780a9a7dc653316c8b2.png