每天一道leetcode92-反转m到n处的链表

乔戈里

发布于 2019-09-17 14:52:21

1.1K0

发布于 2019-09-17 14:52:21

文章被收录于专栏：Java那些事

题目

每天一道leetcode92-反转m到n处的链表分类：链表中文链接： https://leetcode-cn.com/problems/reverse-linked-list-ii/ 英文链接 https://leetcode.com/problems/reverse-linked-list-ii/

题目详述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

题目详解

思路

分两种情况讨论哈，一种是m等于1的，一种是m不等于1的
m等于1的话，简单，就是一个反转链表，如何反转见这篇文章，之前写过；m等于1的话，先反转m-n这些节点，反转完成以后，一开始的头结点就成了最后一个节点，所以反转前把这个节点保留下来，然后反转结束以后把后面的连起来就行；
m不等于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) {
        if(head == null || head.next == null)
            return head;
        if(m != 1)
        {
            ListNode temp = head.next;
            ListNode preFirst = head;//指向反转处的前一个节点值
            for(int i=0;i<m-2;i++)
            {
                temp = temp.next;
                preFirst = preFirst.next;
            }
            //从temp处开始反转链表；
            //由于temp是反转后的最后一个节点记录temp这个节点
            ListNode last = temp;
            ListNode pre = temp;//在这里开始反转链表 老套路
            ListNode pNode = temp.next;
            ListNode next = null;
            for(int i=0;i<n-m;i++)
            {
                next = pNode.next;
                pNode.next = pre;
                pre = pNode;
                pNode = next;
            }
            preFirst.next = pre;
            last.next = pNode;
        }else{
            ListNode pre = head;
            ListNode pNode = head.next;
            ListNode next = null;
            ListNode last = pre;//记录下来这个last节点；
            for(int i=0;i<n-m;i++)
            {
                next = pNode.next;
                pNode.next = pre;
                pre = pNode;
                pNode = next;
            }
            last.next = pNode;//反转后的最后一个节点连接上后续的节点
            return pre;//pre是反转后的头结点；
        }
        return head;
    }
}