[LintCode] Reverse Nodes in k-Group

XGBCCC 发布于2019-08-14 15:12 / 3285人阅读

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;
    }
}

海外云主机私有云 Nodes LintCode Reverse LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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