程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode-- Reverse Linked List II

LeetCode-- Reverse Linked List II

編輯:C++入門知識

LeetCode-- Reverse Linked List II


題目描述:


Reverse a linked list from position m to n. Do it in-place and in one-pass.


For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,


return 1->4->3->2->5->NULL.


Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.


思路:
1. 使用棧來保存m到n之間的數字,其余元素使用隊列保存
2. 在[m,n]區間外時,循環彈出棧內元素到鏈表
3. 在[m,n]區間內,先循環彈出隊列元素到鏈表,再創建棧,最後需要判斷當前head是否為空




實現代碼:




/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        var stack = new Stack();
        var q = new Queue();
        ListNode node = null;
        var c = 1;
		ListNode newNode = null;
        while(head != null)
        {
            if(c >= m && c <=n){
                while(q.Count > 0){
                    var first = MoveNext(ref node , q.Dequeue());
					if(first){
						newNode = node;
					}
                }
                while(c >= m && c<= n){
                    stack.Push(head.val);
                    head = head.next;
                    c++;
                }
				if(head == null){
					 while(stack.Count > 0){
						var first = MoveNext(ref node , stack.Pop());
						if(first){
							newNode = node;
						}
					}
				}
            }
            else{
                while(stack.Count > 0){
                    var first = MoveNext(ref node , stack.Pop());
					if(first){
						newNode = node;
					}
                }
                var f = MoveNext(ref node , head.val);
				if(f)
				{
					newNode = node;
				}
                head = head.next;
				c++;
            }
        }
        
        return newNode;
    }
    
    private bool MoveNext(ref ListNode n , int val){
        if(n == null){
            n = new ListNode(val);
			return true;
        }
        else{
            n.next = new ListNode(val);
            n = n.next;
			return false;
        }
    }
    
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved