美文网首页
LeetCode 92. 反转链表 II

LeetCode 92. 反转链表 II

作者: 怀旧的艾克 | 来源:发表于2019-07-14 15:42 被阅读0次

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

    说明:
    1 ≤ m ≤ n ≤ 链表长度。

    示例:

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

    题解

    java代码如下

    /**
     * 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) {
            int changeLen = n - m + 1;
            ListNode preHead = null;
            ListNode result = head;
            
            while(head != null && m > 1) {
                preHead = head;
                head = head.next;
                m--;
            }
            
            ListNode modifyLastTail = head;
            ListNode newHead = null;
            
            // 中间段逆置,使用新的newHead指针,就地逆置
            while(head != null && changeLen > 0) {
                ListNode ptr = head.next;
                head.next = newHead;
                newHead = head;
                head = ptr;
                changeLen--;
            }
            
            modifyLastTail.next = head;
            
            if(preHead != null) {
                preHead.next = newHead;
            } else {
                result = newHead;
            }
            
            return result;
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode 92. 反转链表 II

          本文链接:https://www.haomeiwen.com/subject/zmzbkctx.html