leetcode(92)

电玩女神 2021-12-17 12:35 102阅读 0赞

今天在研究leetcode第92题，下面是我的答案，根据是否从第一个元素开始进行分情况处理：

/**
     * 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) {
            ListNode start = head;
            ListNode now = head;
            Stack<ListNode> stack = new Stack();
            boolean index0 = true;
            for(int i = 0; i < n; i++){
                if(i < m - 1){
                    start = now;
                    now = now.next;
                    index0 = false;
                    continue;
                } else if(i == m - 1){
                    stack.push(now);
                    now = now.next;
                } else if(i <= n - 1 && m != n){
                    stack.push(now);
                    now = now.next;
                } else {
                    break;
                }
            }
            if(!index0){
                while(!stack.isEmpty()){
                    start.next = stack.pop();
                    start = start.next;
                }
                start.next = now;
            } else {
                head = start = stack.pop();
                while(!stack.isEmpty()){
                    start.next = stack.pop();
                    start = start.next;
                }
                start.next = now;
            }
            return head;
        }
    }

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List II.
    Memory Usage: 34.3 MB, less than 100.00% of Java online submissions for Reverse Linked List II.

这是别人的方案：[https://www.cnblogs.com/Deribs4/p/8414109.html][https_www.cnblogs.com_Deribs4_p_8414109.html]

/**
    添加头节点，反转链表某个连续部分
     * 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) return head;
            ListNode dummy = new ListNode(0);
            dummy.next = head;//链表问题可以先创建一个头结点
            ListNode pre = dummy;
            for(int i = 0; i < m - 1; i++) pre = pre.next;//移动m-1次
            ListNode start = pre.next;
            ListNode then = start.next;
            for(int i = 0; i < n - m; i++) {//需要将start后面的n-m个点陆续反转
                start.next = then.next;//start的后面指向then的后面
                then.next = pre.next;//then的后面指向pre的后面，相当于将then插入pre和pre.next之间
                pre.next = then;//pre的后面是then
                then = start.next;//完成一个元素的反转后，then指向下一个准备被反转（插入pre和pre.next之间）的节点
            }
            return dummy.next;
        }
    }

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List II.
    Memory Usage: 34.1 MB, less than 100.00% of Java online submissions for Reverse Linked List II.

[https_www.cnblogs.com_Deribs4_p_8414109.html]: https://www.cnblogs.com/Deribs4/p/8414109.html