当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点

LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点

题目描述

92 Reverse Linked List II
https://leetcode-cn.com/problems/reverse-linked-list-ii/

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

相似题目

LeetCode.206.Reverse Linked List 反转链表
LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点
LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表


解题过程

反转链表的第m到n个结点
双指针,cur指向m结点,pre指向m的前一个结点,从m+1到n依次插入到pre之后即可。
时间复杂度 O(n),空间复杂度 O(1)

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (null == head || null == head.next || m == n) {
        return head;
    }
    // 头结点
    ListNode newHead = new ListNode(0);
    newHead.next = head;
    ListNode pre = newHead, cur = head;
    for (int i = 1; i < n; i++) {
        if (i < m) {
            // cur移到需要反转的起始结点m,pre是前一个结点
            pre = cur;
            cur = cur.next;
        } else {
            // 从m+1到n,依次插入到pre后即可
            ListNode temp = cur.next;
            cur.next = cur.next.next;
            temp.next = pre.next;
            pre.next = temp;
        }
    }
    return newHead.next;
}

GitHub代码

algorithms/leetcode/leetcode/_092_ReverseLinkedList2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_092_ReverseLinkedList2.java


上一篇 Elasticsearch-基础及使用

下一篇 LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

阅读
评论
291
阅读预计1分钟
创建日期 2020-02-20
修改日期 2020-02-20
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论