[LintCode] Reverse Nodes in k-Group

XGBCCC 發布于2019-08-14 15:12 / 3447人閱讀

Problem

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

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.

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

Solution

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        int i = 1;
        while (head != null) {
            if (i%k != 0) {
                head = head.next;
            } else {
                pre = reverse(pre, head.next);
                head = pre.next;
            }
            i++;
        }
        return dummy.next;
    }
    
    private ListNode reverse(ListNode pre, ListNode after) {
        ListNode cur = pre.next, next = pre.next.next;
        while (next != after) {
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
            next = cur.next;
        }
        return cur;
    }
}

GPU云服務器云服務器 Nodes LintCode Reverse LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65441.html

【LC總結】翻轉鏈表 Swap in Pairs, Reverse in k-Group, Reve

摘要：注意這里，只要走到第位 Swap Nodes in Pairs For example,Given 1->2->3->4, you should return the list as 2->1->4->3. Solution public class Solution { public ListNode swapPairs(ListNode head) { if...

Steve_Wang_ 2019-08-14 14:55 評論0 收藏0
[Leetcode] Swap Nodes in Pairs Reverse Nodes in k-

摘要：三指針法復雜度時間空間思路基本的操作鏈表，見注釋。注意使用頭節點方便操作頭節點。翻轉后，開頭節點就成了最后一個節點。 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should ...

TZLLOG 2019-08-14 12:45 評論0 收藏0
[LintCode] Reorder List [鏈表綜合題型]

摘要：鏈表題目的集合雙指針法找中點，分割，合并，翻轉，排序。主函數對于長度為或的鏈表，返回找到中點分割鏈表并翻轉后半段為與前半段合并。當移動到最后一個元素，正好移動到整個鏈表的頭部。 Problem Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln reorder it to: L0 → Ln → L1 → Ln-1 → L2 → L...

王軍 2019-08-14 15:32 評論0 收藏0
[LintCode] Palindrome Linked List

摘要： Problem Implement a function to check if a linked list is a palindrome. Example Given 1->2->1, return true. Key create new list nodes: ListNode pre = null; //null, 1-2-3-4 //1-null, 2-3-4 //2-1...

Tamic 2019-08-14 15:12 評論0 收藏0
[LintCode] Swap Two Nodes in Linked List

摘要：建立結點，指向可能要對進行操作。找到值為和的結點設為，的前結點若和其中之一為，則和其中之一也一定為，返回頭結點即可。正式建立，，以及對應的結點，，然后先分析和是相鄰結點的兩種情況是的前結點，或是的前結點再分析非相鄰結點的一般情況。 Problem Given a linked list and two values v1 and v2. Swap the two nodes in th...

wua_wua2012 2019-08-14 14:41 評論0 收藏0