当前位置：网站首页>Yyds dry inventory interview must brush top101: specified interval reversal in the linked list

Yyds dry inventory interview must brush top101: specified interval reversal in the linked list

2022-07-27 17:46:00 【51CTO】

1. sketch ：

describe

Set the number of a node to size Linked list m Position to n Interval reversal between positions , Time complexity required , Spatial complexity . for example ： The list given is , , return .

Data range ： Chain length ,, The value of each node in the linked list meets

requirement ： Time complexity , Spatial complexity

Advanced ： Time complexity , Spatial complexity

Example 1

Input ：

       
       {1,2,3,4,5},2,4
      
1.

Return value ：

       
       {1,4,3,2,5}
      
1.

Example 2

Input ：

Return value ：

2. Code implementation ：

       
       import java.util.*;
       
/*
       
 * public class ListNode {
       
 *   int val;
       
 *   ListNode next = null;
       
 * }
       
 */
       
public class Solution {
       
    /**
       
     * 
       
     * @param head ListNode class  
       
     * @param m int integer  
       
     * @param n int integer  
       
     * @return ListNode class 
       
     */
       
       //  Solution 1 ： Double pointer ( Two traversal )
       
       // explain ： Easy to understand , The following notes will use left,right Take the place of m,n node  
       
    public ListNode reverseBetween (ListNode head, int m, int n) {
       
             // Set the virtual head node 
       
        ListNode dummyNode = new ListNode(-1);
       
        dummyNode.next = head;
       
        ListNode pre = dummyNode;
       
        //1. go left-1 Step to left Previous node of 
       
        for(int i=0;i<m-1;i++){
       
            pre = pre.next;
       
        }
       
        //2. go roght-left+1 Step to right node 
       
        ListNode rigthNode = pre;
       
        for(int i=0;i<n-m+1;i++){
       
            rigthNode = rigthNode.next;
       
        }
       
        //3. Intercept a sub linked list 
       
        ListNode leftNode = pre.next;
       
        ListNode cur = rigthNode.next;
       
        //4. Cut off the link 
       
        pre.next=null;
       
        rigthNode.next=null;
       
        //5. Reverse local list 
       
        reverseLinkedList(leftNode);
       
        //6. Connect back to the original linked list 
       
        pre.next = rigthNode;
       
        leftNode.next = cur;
       
        return dummyNode.next;
       
    }
       
    // Reverse local list 
       
    private void reverseLinkedList(ListNode head){
       
        ListNode pre = null;
       
        ListNode cur = head;
       
        while(cur!=null){
       
            //Cur_next  Point to cur The next node of the node 
       
            ListNode Cur_next = cur.next;
       
            cur.next = pre;
       
            pre = cur;
       
            cur = Cur_next ;
       
        }
       
    }
       
}
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/208/202207271532361545.html

当前位置：网站首页>Yyds dry inventory interview must brush top101: specified interval reversal in the linked list

Yyds dry inventory interview must brush top101: specified interval reversal in the linked list

边栏推荐

猜你喜欢

随机推荐