Leetcode92: Reverse Linked List II 翻转链表问题

问题描述

给定一个链表，要求翻转其中从m到n位上的节点，返回新的头结点。

Example

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

Output: 1->4->3->2->5->NULL

分析

这题解法比较直接，可以定义一个fakeNode, 首先拼接 1 到 m - 1的节点，然后拼接链表 m 到 n reverse 之后的结果，最后拼接剩下的节点。reverse链表这里主要使用stack和3指针方法。

解法

方法1. Stack

 ListNode fakeHead = new ListNode(0);

        ListNode cur =fakeHead;

        ListNode curH = head;

        int cnt = n - m + 1;

        //链接 1到m - 1节点

        while(m > 1){

            cur.next = curH;

            curH = curH.next;

            cur = cur.next;

            m--;

        }

        cur.next = null;

        //链接m 到 n 翻转之后的结果

        Stack<ListNode> stack =new Stack();

        for(int i = 0; i < cnt; i++){

            stack.push(curH);

            curH = curH.next;

        }

        while(!stack.isEmpty()){

            cur.next = stack.pop();

            cur = cur.next;

        }

        //链接 n + 1 之后的链表

        cur.next = curH;

        return fakeHead.next;

时间复杂度O(n)，空间复杂度O(n)

方法2. 3指针

 public ListNode reverseBetween(ListNode head, int m, int n) {

        ListNode fakeHead = new ListNode(0);

        ListNode cur =fakeHead;

        ListNode curH = head;

        int cnt = n - m + 1;

        //链接 1到m - 1节点

        while(m > 1){

            cur.next = curH;

            curH = curH.next;

            cur = cur.next;

            m--;

        }

        cur.next = null;

        //链接m 到 n 翻转之后的结果

        ListNode pre = null;

        ListNode next = curH.next;

        ListNode tail =curH;

        for(int i = 0; i < cnt; i++){

            curH.next = pre;

            pre = curH;

            curH = next;

            if(next != null){

                next = next.next;

            }

        }

        cur.next = pre;

        //链接 n + 1 之后的链表

        tail.next = curH;

        return fakeHead.next;

    }

时间复杂度O(n)，空间复杂度O(1)

巴特西

Leetcode92: Reverse Linked List II 翻转链表问题

问题描述

分析

解法

方法1. Stack

方法2. 3指针

最新文章

热门文章