链表内指定区间反转_

Java

摆渡书生

自己的想法，有些麻烦

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode tmp = head;
        ListNode pre, cur, preNode = null, tailNode = null;
        int i = 0;

        //范围包含头结点，则创建一个结点使得 next 域指向 head
        if (m == 1) {
            preNode = new ListNode(0);
            preNode.next = head;
        }

        //遍历链表找到起始节点
        while (tmp != null) {
            //若范围不包含头节点，则记录范围两头相邻的节点preNode、tailNode
            if (i == m - 2) {
                preNode = tmp;
            }
            if (i == n) {
                tailNode = tmp;
            }

            tmp = tmp.next;
            i++;
        }

        pre = null;
        cur = preNode.next;

        //反转链表
        while (cur != null) {

            if (cur == preNode.next) {
                pre = tailNode;
            }

            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;

            if (cur == tailNode) {
                preNode.next = pre;
                break;
            }
        }

        if (m == 1) {
            return preNode.next;
        }

        return head;
    }
}

发表于 2024-05-15 17:36:39 回复(0)

Java

牛客336302566号

public ListNode reverseBetween (ListNode head, int m, int n) {

// write code here

if (m == n) {

return head;

}

int index = 1;

ListNode start = new ListNode(0);

start.next = head;

ListNode mIndex = head;

while (index < m) {

index++;

start = mIndex;

mIndex = mIndex.next;

}

ListNode startNext = start.next;

while (mIndex.next != null & index < n) {

start.next = mIndex.next;

mIndex.next = start.next.next;

start.next.next = startNext;

startNext = start.next;

index++;

}

return m == 1 ? startNext : head;

}

发表于 2024-05-09 14:35:44 回复(0)

Java

阿宗阿

public class Solution {

/**

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

 *

 *

@param head ListNode类
@param m int整型
@param n int整型

@return ListNode类

*/

public ListNode reverseBetween (ListNode head, int m, int n) {

  // write code here

  ListNode root = new ListNode(-1);

  root.next = head;

  ListNode left = null;

  ListNode right = null;

  ListNode begin = root;

  ListNode end = root;

  for(int i=0;i<m;i++){

      left = begin;

      begin = begin.next;

  }

  for(int i=0;i<n;i++){

      end = end.next;

      right = end.next;

  }

  left.next = null;

  end.next = null;

  reverseNode(begin);

  left.next = end;

  begin.next = right;

  return root.next;

}

public ListNode reverseNode (ListNode head){

  if(head == null) {

      return null;

  }

  ListNode pre = null;

  ListNode next = null;

  while(head != null) {

      next = head.next;

      head.next = pre;

      pre = head;

      head = next;

  }

  return pre;

}

编辑于 2024-03-17 16:35:26 回复(1)

Java

牛客_1164649494

写的有点答辩，就是从前往后依次将节点指向最后一个节点，最后一个节点会变

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode pre=new ListNode(-1);
        pre.next=head;
        ListNode cp=head;
        ListNode cur=head;
        ListNode start=pre;
        int left=1;
        while(left<m){start=cp;cp=cp.next;cur=cur.next;left++;}
        while(left<n){cur=cur.next;left++;}
        ListNode last=cur.next;
        int s=m;
        while(s<=n){
            ListNode next=cp.next;
            cp.next=last;
            last=cp;
            cp=next;
            s++;
        }
        start.next=cur;
        return pre.next;



        
        // write code here
    }
}

编辑于 2024-03-09 11:51:43 回复(0)

Java

Rlin99

public ListNode reverseBetween (ListNode head, int m, int n) {
        //此情况无需反转
        if(m == n ) {
            return head;
        }
        //虚拟节点，防止从第一个节点就开始反转（m=1的情况）
        ListNode res = new ListNode(-1);
        res.next = head;

        //指针，指向反转节点的 前一个节点，用于连接 反转后的节点
        ListNode perfix = res;
        ListNode p = head;
        //找到第一个反转的开始节点 
        while(p.next != null && m > 1) {
            p = p.next;
            perfix = perfix.next;
            m--;
            n--;
        }
        ListNode reversNode = null;
        //开始反转
        while(p != null && n > 0) {
            ListNode tmp = p.next;
            p.next = reversNode;
            reversNode = p;
            p = tmp;
            n--;
        }
        //reversNode 就是反转后的节点
        perfix.next = reversNode;
        ListNode s = reversNode;
        //指针s，找到反转后的链表 的最后一个节点
        while (s.next != null) {
            s = s.next;
        }
        //将这个节点连接上p
        s.next = p;
        return res.next;
    }

发表于 2024-03-08 23:42:58 回复(0)

Java

牛客119190309号

public ListNode reverseBetween (ListNode head, int m, int n) {

// write code here

if(head == null || head.next == null){

return head;

}

List<Integer> list = new ArrayList<>();

while(head != null){

list.add(head.val);

head = head.next;

}

if(list.size() == 1){

return head;

}

List<Integer> list2 = list.subList(m-1,n);

Collections.reverse(list2);

int index = 0;

for(int i=m-1;i<n-1;i++){

int num = list2.get(index);

list.set(i,num);

index++;

}

ListNode temp = null;

ListNode res = null;

for(int i=0;i<list.size();i++){

int num = list.get(i);

ListNode node = new ListNode(num);

if(i == 0){

temp = node;

res = temp;

} else {

temp.next = node;

temp = node;

}

return res;

}

编辑于 2024-02-28 21:36:58 回复(0)

Java

牛客710408623号

import java.util.*;

/*

* public class ListNode {

* int val;

* ListNode next = null;

* public ListNode(int val) {

* this.val = val;

* }

*/

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类

* @param m int整型

* @param n int整型

* @return ListNode类

*/

public ListNode reverseBetween (ListNode head, int m, int n) {

// write code here

if (m == n) {

return head;

}

int c = Math.min(m, n);

int f = Math.max(m, n);

n = f;

m = c;

int count = 1;

ListNode newTemp = null;

ListNode finalN = new ListNode(0);

ListNode cur = finalN;

while (head != null) {

if (count < m||count>n) {

cur.next = new ListNode(head.val);

cur = cur.next;

}

if (count >= m && count <= n) {

ListNode t1 = new ListNode(head.val);

t1.next = newTemp;

newTemp = t1;

}

if (count==n) {

while(newTemp!=null){

cur.next = new ListNode(newTemp.val);

cur=cur.next;

newTemp=newTemp.next;

}

head = head.next;

count++;

}

return finalN.next;

}

编辑于 2024-01-20 17:24:08 回复(0)

Java

态度认真的IT实习生

import java.util.*;

/*

* public class ListNode {

* int val;

* ListNode next = null;

* public ListNode(int val) {

* this.val = val;

* }

*/

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类

* @param m int整型

* @param n int整型

* @return ListNode类

*/

public ListNode reverseBetween (ListNode head, int m, int n) {

if(m==n||head==null)return head;

ListNode go = head;

ListNode left=null;

ListNode right=null;

ListNode ll=null;

ListNode rr=null;

for(int i=1;i<m;i++){

ll=go;

go=go.next;

}

if(left==null)left=head;

go=head;

for(int i=1;i<=n;i++){

right=go;

go=go.next;

}

if(ll!=null)

left=ll.next;

if(right!=null)

rr=right.next;

ListNode pre=null;

ListNode t = left;

while(left!=rr){

ListNode temp = left.next;

left.next=pre;

pre=left;

left=temp;

}

left=t;

if(left!=null)

left.next=rr;

if(ll!=null)

ll.next=right;

if(ll==null)return right;

return head;

}

发表于 2023-12-14 17:21:10 回复(0)

Java

GuofanLee

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类

* @param m int整型

* @param n int整型

* @return ListNode类

*/

public ListNode reverseBetween (ListNode head, int m, int n) {

if (head == null) {

return null;

}

ListNode beforeM = null;

ListNode pre = null;

ListNode cur = head;

for (int i = 1; i <= n; i++) {

if (i <= m) {

if (i == m) {

beforeM = pre;

}

pre = cur;

cur = cur.next;

} else {

ListNode temp = cur.next;

cur.next = pre;

pre = cur;

cur = temp;

}

if (beforeM != null) {

beforeM.next.next = cur;

beforeM.next = pre;

return head;

} else {

head.next = cur;

return pre;

}

发表于 2023-11-30 23:35:56 回复(0)

Java

vector2024

https://www.algomooc.com/3088.html，这个图很棒

发表于 2023-11-10 10:39:35 回复(0)

Java

进入人才池

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {

        // dummy -> l1 -> l2 -> l3， 反转 l2

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 断开
        ListNode p = dummy;
        int idx = 0;
        while ( idx < m-1 ) {
            p = p.next;
            idx ++;
        }
        ListNode l1Tail = p, l2Head = p.next;
        p.next = null;

        // 断开
        p = l2Head;
        while ( idx < n-1 ) {
            p = p.next;
            idx ++;
        }
        ListNode l3Head = p.next;
        p.next = null;

        ListNode[] headTail = reverse(l2Head);

        l1Tail.next = headTail[0];
        headTail[1].next = l3Head;

        return dummy.next;

    }
    ListNode[] reverse(ListNode head) {
        ListNode pre = null, cur = head, nxt = null;
        while ( cur != null ) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return new ListNode[]{pre, head};
    }
}

发表于 2023-10-18 23:49:07 回复(0)

Java

练习时长两年半的太平湖水怪很理智

    // 方法一：
    public ListNode reverseBetween (ListNode head, int m, int n) {

        // 用于指向头结点，在完成反转后返回，防止头节点丢失
        ListNode dummy = new ListNode(-1);
        // next指向头节点
        dummy.next = head;
        ListNode pre = dummy;
        // 将pre移至m节点的前一个节点
        for(int i= 1;i<m;i++){
            pre = pre.next;
        }
        // 指向m节点
        ListNode cur = pre.next;
        // 初始化cur节点的下一节点
        ListNode temp = null;
        // 进行n-m次反转,反转过程中，cur节点一直不变，因为cur节点最终会位于反转链的末尾，
        // 每一次循环都完成一次将原cur链中cur节点的下一节点放至反转链的头节点位置，并与pre节点拼接的过程
        for(int i = 0;i<(n-m);i++){
            temp = cur.next;
            //cur节点指向它的下下节点,即删除pre链和cur链中的temp节点(cur的下一个节点)
            cur.next = temp.next;
            // 使temp节点指向pre节点的下一节点，即在pre节点的一下节点前拼接temp节点
            temp.next = pre.next;
            // 在pre节点后拼接temp链
            pre.next = temp;
        }
        // 如果从第一个节点开始反转，此时pre = dummy，则pre.next = temp即为dummy.next = temp，首节点会变化
        // 如果不是从第一个节点开始反转，则pre != dummy,则dummy.next =  head，而head在反转过程中未发生变化，首节点不变化
        // 这保证了dummy一直指向头结点，因此不返回head或者pre，而是返回dummy.next
        return dummy.next;
    }

    // 方法二：
    // 为什么我想的这么复杂！！！！    
    public ListNode reverseBetween2 (ListNode head, int m, int n) {    

        // 用于计数
        int count = 0;
        // 当前节点
        ListNode cur = head;
        // 反转串的头结点
        ListNode headOfReverse = null;
        // 反转串的尾节点
        ListNode tailOfReverse = null;
        // 从首节点后任意节点开始反转
        if (m > 1) {
            // 反转串前第一个不反转的节点
            ListNode node = null;
            while (count <= n) {
                count++;
                // 记录反转串的尾节点
                if (count == m) tailOfReverse = cur;
                // 开始反转
                if (count >= m && count <= n) {
                    ListNode temp = cur.next;
                    cur.next = headOfReverse;
                    headOfReverse = cur;
                    cur = temp;
                // 未开始反转时
                } else if (count<n){
                    // 记录反转串前第一个不反转的节点
                    node = cur;
                    // 当前节点后移
                    cur = cur.next;
                } 
            }
            // 拼接反转串前第一个不反转的节点与反转串
            node.next = headOfReverse;
            // 拼接反转串的尾节点与反转串后不反转的节点
            tailOfReverse.next = cur;
            // 返回原头结点
            return head;
        // 首节点开始反转
        } else {
            cur = head;
            while (count <= n) {
                count++;
                // 记录反转串的尾节点
                if (count == m) tailOfReverse = head;
                // 开始反转
                if (count >= m && count <= n) {
                    ListNode temp = cur.next;
                    cur.next = headOfReverse;
                    headOfReverse = cur;
                    cur = temp;
                }
            }
            // 拼接反转串的尾节点与反转串后不反转的节点
            tailOfReverse.next = cur;
            // 反转串的头节点成为新的头节点，返回反转串的头结点
            return headOfReverse;
        }
    
    }

发表于 2023-09-21 16:52:00 回复(0)

Java

最美不过初见2

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //res 用于保存最终结果
        ListNode res = new ListNode(-1);
        ListNode tail = res;
        ListNode p = head;
        for (int i = 1; i < m; i++) {
            ListNode tmp = p.next;
            tail.next = p;
            tail = p;
            p.next = null;
            p = tmp;
        }
        ListNode s = null;
        for (int j = m; j <= n; j++) {
            ListNode tmp = p.next;
            p.next = s;
            s = p;
            p = tmp;
        }
        tail.next = s;
        ListNode cur=s;
        while(cur.next!=null){
            cur=cur.next;
        }
        if (p != null) {
            cur.next = p;

        }
        return res.next;
    }
}

发表于 2023-09-10 21:46:50 回复(0)

Java

刷题inging

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {

        if (head == null) {
            return null;
        }
        //创建一个虚拟头节点,让整个单链表所有结点处在统一地位方便逻辑处理,dum是一个指向这个链表头结点的指针，它指向的结点的值为0
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode pre = dum;
        ListNode cur = head;
        //找到m结点
//过程中，随着cur往链表右边移动，pre指针同样也存储了1到m结点的指向
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        for (int j = 0; j < n - m; j++) {
            ListNode zc = cur.next;
            cur.next = zc.next;
            zc.next = pre.next;
            pre.next = zc;
        }
        // write code here
        return dum.next;
    }
}

发表于 2023-08-13 22:01:44 回复(0)

Java

阿阿阿阿K

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //m前一个节点
        ListNode first = dummy;

        int id = 0;
        while(id++<m-1){
            first = first.next;
        }
        //m节点
        ListNode second = first.next;
        ListNode cur = second;

        ListNode pre = null;
        //n这个节点需要进入，因为是当前节点往前反转
        while(id++<=n){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //出来后，pre就是n节点，cur就是n后面的节点
        //first连接pre
        first.next = pre;
        //second连接cur
        second.next = cur;
        return dummy.next;
    }
}

发表于 2023-08-13 16:04:57 回复(0)

Java

秃驴应该痛

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
     //本题难点：空指针问题和控制反转区间
     //可以加入头结点来解决反转区间的问题（主要是解决从head到n区间的问题）
     //思路：先找到反转区间的前一个结点和末尾的后一个结点，方便连接
     //然后对反转区间进行迭代头插法（注意控制次数），最后进行连接。
     //时间O（N），空间O（1）
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m==n) {
            return head;
        }
        ListNode Head=new ListNode(-1);
        ListNode head1=Head;//分别记录区间的前一个，和末尾的后一个
        ListNode tail1=head;
        Head.next=head;
        int n1=n;
        int m1=m-1;
        while(m1>0) {
            head1=head1.next;
            m1--;
        }
        while(n1>0) {
            tail1=tail1.next;
            n1--;
        }
        ListNode head2=null;//反转区间的头结点
        //cur和tmp用来迭代
        ListNode cur=head1.next;
        ListNode tmp=cur;
        int num=n-m+1;
        while(num>0) {
            tmp=cur.next;
            if(head2==null) {
                head2=cur;
                cur.next=tail1;
            }
            else {
                cur.next=head2;
                head2=cur;
            }
            cur=tmp;
            num--;
        }
        if(head1!=null)
        head1.next=head2;
        return Head.next;
    }
}

发表于 2023-07-18 13:31:45 回复(0)

Java

抓住努力的尾巴

借助栈进行局部反转

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //1、判断 m == n
        if (m == n) {
            return head;
        }
        //2、m < n
        //简便方法（栈）
        int len = n - m + 1;
        Stack<ListNode> sta = new Stack<>();

        ListNode cur = head;
        ListNode pre = null;
        ListNode after = null;

        //m是头节点
        if (m == 1) {
            sta.push(cur);
            cur = cur.next;
            while (cur != null && len != 1) {
                sta.push(cur);
                cur = cur.next;
                len--;
            }
            after = cur;
            head = sta.pop();
            cur = head;
            while (!sta.isEmpty()) {
                cur.next = sta.pop();
                cur = cur.next;
            }
            cur.next = after;
            return head;
        } else {
            //m 不是 头节点
            sta.clear();

            cur = head;

            int count = 1;

            //找到 m 位置的前一个节点
            while (cur != null && count < m - 1) {
                cur = cur.next;
                count++;
            }
            pre = cur;
            cur = cur.next;
            len = n - m + 1;
            while (len-- > 0) {
                sta.push(cur);
                cur = cur.next;
            }
            after = cur;
            while (!sta.isEmpty()) {
                pre.next = sta.pop();
                pre = pre.next;
            }
            pre.next = after;
            return head;
        }
    }
}

发表于 2023-07-10 10:52:15 回复(0)

Java

做则必成的勇气和信心

 public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        for(int i=1;i<m;i++){
            pre=pre.next;
        }
        ListNode right;
        right=pre;
        for(int i=m;i<n+1;i++){
            right=right.next;
        }
        ListNode left;
        left=pre.next;
        ListNode cur=right.next;
        //断开
        pre.next=null;
        right.next=null;
        reverse(left);
        pre.next=right;
        left.next=cur;
        return dummy.next;
    }
    public void reverse(ListNode cur){
        ListNode pre=null;
        while(cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
    }

发表于 2023-06-18 16:06:19 回复(0)

链表内指定区间反转

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

借助栈进行局部反转

问题信息

热门推荐

通过挑战的用户

相关试题