首页 > 代码库 > 【leetcode】reverse Nodes in k-groups

【leetcode】reverse Nodes in k-groups

2024-07-07 19:27:01   224人阅读

问题：

给定一个链表的头指针，以及一个整数k，要求将链表按每k个为一组，组内进行链表逆置。少于k个的部分不做处理。

分析：

个人觉得问题的重点是熟悉链表的就地逆置操作，就是头插法。其他的考察点如果还有的话，就的细心程度。

实现：

   void reverseList(ListNode *&pre, ListNode *head)
{
	ListNode *tail = NULL;
	while (head)
	{
		ListNode* next = head->next;
		head->next = pre->next;
		pre->next = head;
		if(tail == NULL)
			tail = head;
		head = next;
	}
	pre = tail;
}

上面所示函数，实现将head指示的链表进行逆置链接在pre的后面。
void hh(ListNode*& pre, ListNode*head, int k){

	if(head == NULL || k <= 1)
	{
        pre->next = head;
		return;
	}
	int dis = 1;
	ListNode* tail = head;
	while (dis < k && tail)
	{
		++dis;
		tail = tail->next;
	}
	if(tail == NULL)
	{
		pre->next = head;
		return;
	}
	ListNode *newhead = tail->next;
	tail->next = NULL;
	reverseList(pre, head);
	hh(pre, newhead, k);
}

上面的函数，对给定的head 指示的链表，找出首个k个结点的链表区间，作为进行逆置的对象，并找到下一个逆置区间的开始结点，进行递归。
其实这里进行递归有点那个，唯一的解释就是懒。
ListNode *reverseKGroup(ListNode *head, int k) {
	ListNode* newHead = new ListNode(-1);
	ListNode* pre = newHead;

	hh(pre, head, k);
	return newHead->next;
}

下面的另外一种实现。
	ListNode *reverseKGroup(ListNode *head, int k) {
		if (head == NULL || head->next == NULL || k == 1)
			return head;
		ListNode *new_head = new ListNode(-1);
		new_head->next = head;
		int visited_len = 0;
		ListNode *pre, *tail, *travel;
		pre = new_head;
		while (1)
		{
			travel = pre;
			visited_len = 0;
			while (travel != NULL && visited_len < k) 
				{
					travel = travel->next;
					if(travel)
					visited_len++;
			}
			if(visited_len < k) break;

			travel = travel->next;//the next begin position.
			ListNode *p = tail = pre->next;
			pre->next = travel;
			ListNode *q = p->next;
			do{
				p->next = pre->next;
				pre->next = p;
				p = q;
				if(p)
				q = p->next;
			}while(p != travel);
			pre = tail;
		}
		pre = new_head;
		new_head = new_head->next;
		delete pre;
		return new_head;
	}


联系
我们