# 引言

题目链接:https://leetcode.com/problems/reverse-nodes-in-k-group/

# 题目大意

给定一个链表,一次反转链表的 k 个节点 (每 k 个节点翻转一次), 最后返回修改后的列表。

Hint: k 是正整数,并且小于或等于链表的长度。如果节点数不是 k 的倍数,那么最后的剩余节点应该保持不变。

  • 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

# 题解

# 一句话题解

这题算是 24 题 Swap Nodes in Pairs 的进阶版本。使用快慢指针,先行指针先走 k 步,就地转置慢指针与快指针之间的节点,最后处理整个翻转链,重复这个过程直至结束

# 复杂度

时间复杂度 O(kn) , k 是需要翻转的区间长度

空间复杂度 O(1)

# AC 代码

c++ 版本

/**
 * 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)
    {
        ListNode *ret = new ListNode(-1);
        ret->next = head;
        ListNode *fast = ret;
        ListNode *slow = ret;
        ListNode *tmp1, *tmp2;
        while (nullptr != fast && nullptr != fast->next)
        {
            int n = k;
            while (n && nullptr != fast->next)
            {
                fast = fast->next;
                --n;
            }
            if (n > 0)
            {
                break;
            }
            tmp1 = fast->next;
            tmp2 = slow->next;
            reverseIntervalList(slow->next, fast);
            slow->next->next = tmp1;
            slow->next = fast;
            slow = fast = tmp2;
        }
        return ret->next;
    }
  private:
    void reverseIntervalList(ListNode *begin, ListNode *end)
    {
        ListNode *pre = begin;
        ListNode *cur = begin->next;
        ListNode *tmp;
        while (pre != end)
        {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
    }
};

go 版本

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseIntervalList(begin, end *ListNode) {
	pre, cur := begin, begin.Next
	var tmp *ListNode
	for pre != end {
		tmp = cur.Next
		cur.Next = pre
		pre = cur
		cur = tmp
	}
}
func reverseKGroup(head *ListNode, k int) *ListNode {
	ret := &ListNode{-1, nil}
	ret.Next = head
	fast, slow := ret, ret
	var tmp1, tmp2 *ListNode
	for nil != fast && nil != fast.Next {
		n := k
		for n > 0 && nil != fast.Next {
			fast = fast.Next
			n--
		}
		if n > 0 {
			break
		}
		tmp1 = fast.Next
		tmp2 = slow.Next
		reverseIntervalList(slow.Next, fast)
		slow.Next.Next = tmp1
		slow.Next = fast
		slow, fast = tmp2, tmp2
	}
	return ret.Next
}
更新于 阅读次数