Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Reverse Nodes in k-Group

Leetcode algorithms 第 25 题:Reverse Nodes in k-Group。

题目

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.

For 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

解答

链表操作,将链表以k个元素为单位逆转。直接按照定义进行,将原链表以k个元素为单位进行遍历,然后逆转这k个元素的一段子链表。注意在逆转子链表之前需要先保存好下k个链表的起始地址,以便进入下一轮循环。最后不足k个的链表节点顺序不变,直接接到结果链表中。

具体代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (head == NULL || head->next == NULL || k <= 1) return head;
        
        ListNode dummy(-1), *cur = &dummy;
        while (head != NULL)
        {
            ListNode *tail = head; //找到当前的head和tail
            for (int i = 1; tail != NULL && i < k; i++)
                tail = tail->next;
            if (tail == NULL) break;
            
            cur->next = tail, cur = head; //tail为逆转后的头结点,head则为尾节点
            ListNode *tailNext = tail->next; //保存下k个节点的起始地址
            
            ListNode *p1 = NULL, *p2 = head; //head到tail指针逆转
            while (p2 != tailNext)
            {
                ListNode *tem = p2->next;
                p2->next = p1; 
                p1 = p2, p2 = tem;
            }
            
            head = tailNext; //进入下k个节点
        }
        cur->next = head; //最后不足k个的节点顺序不变
        
        return dummy.next;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论