14191 - Reverse Linked List II   

Status  |  Limits Submit

Description

給定主要執行程式main.c (題號.c)、以及Header檔function.h (題號.h)；請試著完成Header檔中未實現的函式：reversBetween()

 

function.h：

ListNode

  • val (int) 儲存的整數

  • next (struct ListNode*) 代表下一個ListNode的記憶體位置

 

Methods:

- struct ListNode *reverseBetween(struct ListNode *head, int left, int right) – 

  • 需不斷的拜訪傳進的ListNode記憶體的下一個ListNode記憶體(next)直至限定範圍right

  • 將範圍介於left, right 間所有拜訪過的ListNode中的下一個記憶體(next)指向上一個拜訪過的ListNode記憶體

  • 將原先位置left的前一個ListNode記憶體的下一個ListNode記憶體(next)指向反轉後的第一個ListNode記憶體（原先位置right的ListNode記憶體）

  • 將反轉後的最後一項ListNode記憶體(原先位置left的ListNode記憶體)的下一個ListNode記憶體(next)指向原位置right的下一個ListNode記憶體，使經過反轉後的所有節點依然為Linked List

  • 最後回傳Linked List的第一個ListNode記憶體。

 

Hint:

  1. 可以透過迴圈和next來不斷拜訪並取得下一個ListNode

  2. 可以宣告四個struct ListNode *dummyNode, *currNode, *nextNode, *prevNode，用以儲存Linked List的第一個ListNode記憶體和將left, right範圍間ListNode記憶體的下一個ListNode記憶體（next）指向上一個拜訪的ListNode記憶體，並持續拜訪下一個ListNode記憶體

 

 

function.c

#include "function.h"

struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {

  // TODO

} 

Input

left right

n1 n2 n3 n4 n5

 

Note:

  1. left, right 代表需做反轉(reverse)的ListNode範圍

  2. 1 <= left <= right <= 5

  3. 若left = right，則表示不需做反轉

  4. left, right代表Linked List中的第n個ListNode，非Linked List中的ListNode index值

e.g. left: 2, right: 4, Linked List中每個ListNode的val: [1, 2, 3, 4, 5]

       (o) 代表需做反轉的部分為Linked List的[2, 3, 4]

       (x) 代表需做反轉的部分為Linked List的[3, 4, 5]

  1. n1~n5為整數，-2147483648 <= n <= 2147483647

 

Output

輸出符合以下格式：

e.g n1 n4 n3 n2 n5

 

Note:

  1. 無需處理輸出

Sample Input  Download

Sample Output  Download

Partial Judge Code

14191.c

Partial Judge Header

14191.h

Tags




Discuss