Reverse Nodes in k-Group (H)

題目

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

題意

將給定鏈表中的每k個結點按逆序重新排列，不能改變結點內的值，只能改動結點本身，且只能使用\(O(1)\)的空間，

思路

整體上與 24. Swap Nodes in Pairs (M) 的解決方法相似，只是多了2個以上結點的逆序排列，因為只能使用常數的額外空間，所以不能用堆疊來實作逆序，直接使用插入到頭結點之前的方式來實作逆序，

代碼實作

Java

遞回

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pointer = head;
        // 判斷剩余結點數是否達到k，并找到下一個k元組的頭結點
        for (int i = 0; i < k; i++) {
            if (pointer == null) {
                return head;
            }
            pointer = pointer.next;
        }

        ListNode nextHead = pointer;		// 記錄下一個k元組的頭結點
        ListNode first = null;				// 逆序排列時記錄逆序鏈表的頭結點
        pointer = head;
        // 逆序處理
        while (pointer != nextHead) {
            ListNode temp = pointer.next;
            pointer.next = first;
            first = pointer;
            pointer = temp;
        }
        head.next = reverseKGroup(nextHead, k);
        
        return first;
    }
}

迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode ans = new ListNode(0);
        ans.next = head;
        ListNode root = ans;		// 記錄上一個k元組逆序后的最后一個結點

        // 統計結點數
        ListNode pointer = head;
        int num = 0;
        while (pointer != null) {
            num++;
            pointer = pointer.next;
        }

        pointer = ans.next;
        while (num >= k) {
            ListNode first = null;			// 逆序時的頭結點
            ListNode nextRoot = pointer;	// 記錄當前k元組逆序前的第一個結點
            // 逆序處理
            for (int i = 0; i < k; i++) {
                ListNode temp = pointer.next;
                pointer.next = first;
                first = pointer;
                pointer = temp;
            }
            root.next = first;
            root = nextRoot;
            num -= k;
        }
        root.next = pointer;		// 將個數不足k的結點補充到鏈表最后
        
        return ans.next;
    }
}

JavaScript

遞回

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  if (head === null) {
    return null
  }

  let nextHead = head
  for (let i = 1; i <= k; i++) {
    if (nextHead === null) {
      return head
    }
    nextHead = nextHead.next
  }

  let newHead = null
  let tail = head
  while (head !== nextHead) {
    let tmp = head.next
    head.next = newHead
    newHead = head
    head = tmp
  }
  tail.next = reverseKGroup(nextHead, k)
    
  return newHead
}

迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  let len = 0
  let p = head
  while (p !== null) {
    len++
    p = p.next
  }

  let dummy = new ListNode(0, head)
  let tail = dummy
  p = head
  while (len >= k) {
    let nextTail = p
    let newHead = null
    for (let i = 0; i < k; i++) {
      let tmp = p.next
      p.next = newHead
      newHead = p
      p = tmp
    }
    tail.next = newHead
    tail = nextTail
    len -= k
  }
  tail.next = p

  return dummy.next
}

標籤：其他

上一篇：0024. Swap Nodes in Pairs (M)

下一篇：0283. Move Zeroes (E)