[leetcode题解]25.Reverse Nodes in k-Group(链表每k个元素逆置)

这个题很有意思,虽然标的难度为hard,但是其实就是链表相关知识点的一个小综合,比如尾插法,段遍历,双指针操作等。题目给定一个单链表和一个k值,要求将链表中的元素从表头开始每k个元素组成一个组,然后组内的元素进行逆置操作,如果最后一组不满k个元素,则该组中的元素顺序保持不变。特别的,题目中说操作过程中不能改变元素节点的值,只能对整个节点进行操作,这就要求我们要通过链表指针的操作来完成上述过程。

总的思路如上所说,先依次向后确定每个分组,对确定的分组用尾插法进行逆置,然后设置新的起点,重复上述过程即可。

python代码:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        pre = ListNode(-1)
        tail = pre
        
        q = head
        while q is not None:
            #向后查找k个节点
            n = k
            p = q
            while p is not None and n > 0:
                p = p.next
                n -= 1
                
            #如果在查找k个节点的过程中遇到None,则说明
            #后面的节点不够k个节点则直接跳出即可
            if n > 0:
                tail.next = q
                break
            
            #将这K个节点以头插法插入
            end = q
            while q != p:
                t = q.next
                q.next = tail.next
                tail.next = q
                q = t
            tail = end
        return pre.next
        

c++代码:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode *pre = new ListNode(-1), *tail = pre;
        
        ListNode *p = head;
        while(p != NULL)
        {
            ListNode *q = p;
            int cnt = 0;
            for (int i = 0; i < k && q != NULL; ++i)
            {
                q = q->next;
                ++cnt;
            }
            
            if (cnt < k)
            {
                tail->next = p;
                break;
            }
            ListNode *end = p;
            while(p != q)
            {
                ListNode *t = p->next;
                p->next = tail->next;
                tail->next = p;
                p = t;
            }
            tail = end;
        }
        return pre->next;
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]25.Reverse Nodes in k-Group(链表每k个元素逆置)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/91.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注