LEETCODE 25. K 个一组翻转链表

LEETCODE 25. K 个一组翻转链表

题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
k = 2时,应当返回: 2->1->4->3->5
k = 3时,应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

题目地址:
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

题解一

有一道经典的题目,反转链表,将1->2->3->4变成4->3->2->1。反转链表的一个解法是用栈作为辅助结构,将[1,2,3,4]放入栈中,然后依次弹出来,再把弹出来的节点串联起来,这样就变成4->3->2->1了。
对于k个一组反转,我们也可以用同样的方式,只不过这次不是将全部节点放入栈中,而是将k个节点放入栈中,之后再弹出k个节点,并将他们依次串联起来,这样就达到了反转k个节点的效果了。

有个细节需要注意下,比如链表是:
1->2->3->4->5->6->7k=3时,整个链表遍历完后,栈的个数不等于k,此时栈中只有一个元素7
这也简单,只要判断下栈长度不等于k直接退出就可以了。
当然用栈实现其实并不符合题意,只当扩展下思路。

java代码:

class Solution {
	public ListNode reverseKGroup(ListNode head, int k) {
		if(head==null || k<=0) {
			return head;
		}
		//用栈来保存链表的节点
		Stack<ListNode> stack = new Stack<ListNode>();
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode p = dummy;
		int n = k;
		while(p!=null && p.next!=null) {
			ListNode tmp = p.next;
			//不断的将节点加入到栈中
			while(tmp!=null && n>0) {
				stack.add(tmp);
				tmp = tmp.next;
				--n;
			}
			//栈中的第一个元素,就是原链表中的第k个
			//这里备份第k+1个节点,用作后面串联用
			ListNode nextNode = stack.peek().next;
			//n==0说明栈中正好存了k个元素,挨个弹出来并串联起来
			//否则就退出循环
			if(n==0) {
				while(stack.size()>0) {
					p.next = stack.pop();
					p = p.next;
				}
			} else {
				break;
			}
			//假设链表是1->2->3->4->5,k=3
			//栈的内容是[3,2,1],栈中第一个元素的next就是4
			//于是将p.next指向4就可以了
			p.next = nextNode;
			n = k;
		}
		return dummy.next;
	}
}
                                                                                

python代码:

class Solution(object):
	def reverseKGroup(self, head, k):
		if not head or k<=0:
			return head
		# 用栈来保存链表的节点	
		stack = []
		dummy = ListNode(-1)
		dummy.next = head
		p = dummy
		n = k
		while p and p.next:
			tmp = p.next
			# 不断的将节点加入到栈中
			while tmp and n>0:
				stack.append(tmp)
				tmp = tmp.next
				n -= 1
			# 栈中的第一个元素,就是原链表中的第k个
			# 这里备份第k+1个节点,用作后面串联用
			next_node = stack[-1].next
			# n==0说明栈中正好存了k个元素,挨个弹出来并串联起来
			#否则就退出循环
			if n==0:
				while stack:
					p.next = stack.pop()
					p = p.next
			else:
				break
			#假设链表是1->2->3->4->5,k=3
			# 栈的内容是[3,2,1],栈中第一个元素的next就是4
			# 于是将p.next指向4就可以了
			p.next = next_node
			n = k
		return dummy.next
                                                                                   

题解二

只要反转链表弄懂了,反转k个也就不难理解了。
这里我们需要借用反转链表的代码:

	public ListNode reverseList(ListNode head) {
		ListNode pre = null;
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			tmp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
                                                                

反转链表的动态演示如下:

现在我们是反转k个,于是就遍历k个链表,然后将第k个节点的next指向空(防止循环),这样就得到了长度为k的单链表了。
之后我们将长度为k的链表直接交由反转链表函数处理,于是我们就可以得到长度为k的反转链表了。

如果遍历完整个链表,发现最后几个节点的长度不足k,那么直接退出就可以了。
反转的时候需要注意,把长度k的链表前后指向切断,这样就不会出现循环指向了。

java代码:

class Solution {
	public ListNode reverseKGroup(ListNode head, int k) {
		if(head==null || k<=0) {
			return head;
		}
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode p = dummy;
		int n = k;
		//增加一个哨兵节点,之后不断遍历链表
		while(p.next!=null)  {
			ListNode tmp = p;
			//遍历得到k个长度的链表
			while(tmp!=null && tmp.next!=null && n>0) {
				tmp = tmp.next;
				--n;
			}
			//如果k==0说明符合条件,就反转这一组链表
			//反转之前需要将下一个节点保存,并设置next为空,防止循环指向
			//假设链表为1->2->3->4,下面的nextNode就是4,tail是1
			if(n==0) {
				ListNode nextNode = tmp.next;
				ListNode tail = p.next;
				tmp.next = null;
				p.next = reverse(tail);
				tail.next = nextNode;
				p = tail;
				n = k;
			//如果遍历后的链表长度不是k,则不满足反转条件	
			} else {
				break;
			}
		}
		return dummy.next;
	}
	//反转单个链表
	private ListNode reverse(ListNode head) {
		ListNode cur = head;
		ListNode pre = null;
		while(cur!=null) {
			ListNode tmp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}
                                                                                     

python代码:

class Solution(object):
class Solution(object):
	def reverseKGroup(self, head, k):
		if not head or k<=0:
			return head
		dummy = ListNode(-1)
		p,dummy.next = dummy,head
		n = k
		# 反转单个链表
		def reverse(head):
			pre,cur = None,head
			while cur:
				cur.next,pre,cur = pre,cur,cur.next
			return pre
		# 增加一个哨兵节点,之后不断遍历链表	
		while p.next:
			tmp = p
			# 遍历得到k个长度的链表
			while tmp and tmp.next and n>0:
				tmp = tmp.next
				n -= 1
			# 如果k==0说明符合条件,就反转这一组链表
			# 反转之前需要将下一个节点保存,并设置next为空,防止循环指向
			# 假设链表为1->2->3->4,下面的nextNode就是4,tail是1
			if n==0:
				next_node = tmp.next
				tail = p.next
				tmp.next = None
				p.next = reverse(tail)
				tail.next = next_node
				p = tail
				n = k
			# 如果遍历后的链表长度不是k,则不满足反转条件	
			else:
				break
		return dummy.next
                                                                                         

(全文完)

5 次阅读

发表评论

电子邮件地址不会被公开。