LeetCode92. 反转链表 II------Java语言

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode92. 反转链表 II------Java语言，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1330字，纯文字阅读大概需要2分钟。

内容图文

92. 反转链表 II
要求：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
该题目是LeetCode 206. 反转链表的升级版

分析：
①题目要求时间复杂度为O（n）
即只能遍历一次
②如何反转
思路：
①1 ≤ m ≤ n ≤ 链表长度，由于m是最小的，所以当遍历到m的位置时就进行反转
②一直反转到n的位置
首先定义一些指针，用于记录找到m位置的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
           //①若链表的长度小于1，或者m和n为同一个位置，则直接返回该链表
            if (head == null || head.next == null || m == n)
                return head;
            //②考虑链表长度大于1的情况
            //首先定义一个dummy节点，用于链表的遍历
            ListNode dummy = new ListNode(-1);
            dummy.next = head;//将dummy节点和该链表连接起来
            ListNode pre =dummy;//定义一个节点，用于记录m的位置
            for ( int i = 1; i < m ; i++) {
                pre = pre.next;    
            }//pre记录的是m的前一个节点
            ListNode pcur = pre.next;//该位置记录m的节点位置
            //从m位置开始就地反转
            for ( i = m;i<n;i++) {//注意临界条件
                ListNode temp = pcur.next;
                pcur.next = temp.next;
                temp.next = pre.next;
                pre.next = temp;   
            }     
           return dummy.next;//返回用dummy遍历链表的结果
        }
    }

分析：时间复杂度O（n）
空间复杂度O（1）
符合题目要求

内容总结

以上是互联网集市为您收集整理的LeetCode92. 反转链表 II------Java语言全部内容，希望文章能够帮你解决LeetCode92. 反转链表 II------Java语言所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端