92、反转链表II

leetcode

Created At : 2020-07-26 00:19

Count:301 Views 👀 :

Comment:

92、反转链表II
1. 示例:

题解

1、头插法，反转局部链表

92、反转链表II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

$1 ≤ m ≤ n ≤ 链表长度$。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

链接：https://leetcode-cn.com/problems/reverse-linked-list-ii

题解

1、头插法，反转局部链表

/**
 * 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) {
        // 特殊case
        if (m == n) {
            return head;
        }
        // 从第m个元素开始进行头插法
        ListNode dummp = new ListNode(-1);
        ListNode p,q,pre = null;
        p = head;
        // 遍历到第m个结点
        int count = 1;
        while(p != null && count < m) {
            pre = p;
            p = p.next;
            count++;
        }
        // 进行局部链表翻转
        dummp.next = p;
        ListNode t = p;// 记录局部链表的第一个节点
        p = p.next;
        count += 1;
        while(p != null && count <= n) {
            q = p.next;
            p.next = dummp.next;
            dummp.next = p;
            p = q;
            count++;
        }
        t.next = p;// 连接局部链表的最后一个结点

        // 从头开始翻转要更新头结点
        if (m == 1) {
            head = dummp.next;
        } else {// 连接局部链表的第一个结点
            pre.next = dummp.next;
        }
        return head;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com