Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Published
20 hours ago •
Advanced-Frontend
Advanced-Frontend
第 138 题：反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序
我这个是链表尾部开始的，和这个头部开始的差不多
let a = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: {
value: 5,
next: {
value: 6,
next: {
value: 7,
next: {
value: 8,
next: {
}
}
}
}
}
}
}
}
}
function reverseList(_head, _k) {
// 这个求长度可以用循环，用递归长链表容易爆栈
let get_length = (_list) => {
if (_list == null || _list.next == null) {
return 0
}
return get_length(_list.next) + 1
}
let list_length = get_length(_head)
function jump(_list, _step) {
let _t = _list
while (_step-- > 0) {
_t = _t.next
}
return _t
}
function reverse(_node, _step) {
if (_step == 0) {
return _node
}
let _rt = reverse(_node.next, _step - 1)
_node.next.next = _node
_node.next = null
return _rt
}
let _count = list_length % _k
let _link = {
next: _head
}
let _link_postion = jump(_link, _count)
let _next_start_position = null;
while (_count < list_length) {
let _current_start_position = _link_postion.next
_next_start_position = jump(_link_postion, _k + 1)
_link_postion.next = reverse(_current_start_position, _k - 1)
_link_postion = jump(_link_postion, _k)
_link_postion.next = _next_start_position
_count = _count + _k;
}
return _link.next
}
console.log(reverseList(a, 4))
/**
* 反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序
*/
interface ListItem {
next: ListItem | null;
value: any;
}
interface group {
head: ListItem;
tail: ListItem;
}
function reverseEveryKItems(head: ListItem, k: number): ListItem {
let headTmp: ListItem = head;
let groupHeads: Array<ListItem> = [];
let count = 1;
groupHeads.push(headTmp);
// 对列表分组
while (headTmp.next) {
count = count + 1;
if (count === k) {
groupHeads.push(headTmp.next);
count = 0;
}
headTmp = headTmp.next;
}
let lastGroupHead: ListItem;
// 不满K个节点的不反转
if (count !== 0) {
lastGroupHead = groupHeads.pop();
}
// 每K个节点置换，保存head，tail
const groups: Array<group> = groupHeads.map((groupHead) =>
reverseGroupList(groupHead, k)
);
// 将每个反转后的组前尾后头连起来
let reverseHead: ListItem = groups[0].head;
for (let i = 1; i < groups.length; i++) {
let preTail = groups[i - 1].tail;
let curHead = groups[i].head;
preTail.next = curHead;
}
groups[-1].tail.next = lastGroupHead || null;
return reverseHead;
}
/* 每K个列表反转 */
function reverseGroupList(head: ListItem, k: number): group {
let pre: ListItem = head;
let cur: ListItem = head.next;
while (cur && k--) {
let next: ListItem = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return {
head: cur,
tail: head
};
}
大致思路：
- 遍历链表，将每个元素添加到一个栈中
- 判断栈的长度，达到指定长度后，出栈，即可反转
- 若最后一次栈的长度没有达到指定长度，则将这个栈当作队列操作，直接出队
实现如下：
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
print() {
let pointer = this;
let result = '';
while(pointer) {
result += pointer.value + '>';
pointer = pointer.next;
}
console.log(result.substring(0, result.length - 1));
}
}
function reverseLinkedListByk(linkedList, k) {
if (!linkedList) {
return null;
}
if (k < 1) {
return linkedList;
}
const stack = [];
let resultHead = null;
let resultPointer = null;
let traversePointer = linkedList;
while(traversePointer) {
const copy = traversePointer;
traversePointer = traversePointer.next;
copy.next = null;
stack.push(copy);
if (stack.length == k) {
while(stack.length) {
const node = stack.pop();
if (!resultHead) {
resultHead = resultPointer = node;
} else {
resultPointer.next = node;
resultPointer = resultPointer.next;
}
}
}
}
if (stack.length && stack.length < k) {
while(stack.length) {
const node = stack.shift()
resultPointer.next = node;
resultPointer = resultPointer.next;
}
}
return resultHead;
}
const linkedList = new Node(5);
n1 = new Node(8);
n2 = new Node(3);
n3 = new Node(6);
n4 = new Node(9);
n5 = new Node(1);
n6 = new Node(10);
n7 = new Node(39);
linkedList.next = n1
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
linkedList.print();
console.log('----------');
let reversed = reverseLinkedListByk(linkedList, 3);
reversed.print();
楼上的各位，这题用数组做就没意思了啊 纯链表加索引解决的思路: 拆分为2个函数
- 只反转链表
- 在找到需要反转的链表，用 1 去反转
每一轮循环中，将链表视为
pre => start => *** => end => next
我们翻转 start => *** => end 这一段, 变为 pre end => *** => start next 再将原链表和翻转后的合并即可，然后寻找下一段要反转的链表继续循环 pre => end => *** => start => next
// 定义链表节点
class Node {
constructor(v, last) {
this.next = null
this.value = v
if (last) {
last.next = this
}
}
}
let head = makeList(10)
console.info(toString(head))
head = invert(head, 3)
console.info(toString(head))
// 原链表: 0,1,2,3,4,5,6,7,8,9
// 反转后: 2,1,0,5,4,3,8,7,6,9
// ---- 核心思想 -----
/**
* 链表每m个节点反转
* @param {*} head
* @param {*} n
*/
function invert(head, n) {
let pre = new Node(999, null)
pre.next = head
let start = head
let end = head
// 缓存头
head = pre
let count = 1
while (start && end) {
// 查找需要反转的链表 end 节点
if (count < n) {
count++
end = end.next
} else {
count = 1
// 缓存对 end 之后的链表的索引
let next = end.next
// 反转 start -> ** -> end 这段链表
revert(start, next)
// 反转成功后, end 节点是新链表的头了, 而 start 是尾了
pre.next = end
// 反转的链表连上剩下的链表
start.next = next
// 初始化下一段要反转的链表段
pre = start
start = next
end = next
}
}
return head.next
}
/**
* 给定一个链表头和结束标记进行反转
* @param {*} start
* @param {*} endTag
*/
function revert(start, endTag) {
let temp
let pre = null
while (start !== endTag) {
temp = start.next
start.next = pre
pre = start
start = temp
}
return pre
}
// ----工具-----
// 构造一个链表
function makeList(length) {
const head = new Node(-1, null)
Array.from({length}, (_, i) => i).reduce((last, key) => new Node(key, last), head)
return head.next
}
// 打印链表
function toString(head) {
let temp = new Node(999, null)
temp.next = head
let show = []
while ((temp = temp.next)) {
show.push(temp.value)
}
return show.join(',')
}
// 创建链表
function createLinkList(...args) {
const res = {};
let current = res;
while (args.length) {
current.value = args.shift();
current.next = {};
current = current.next;
}
return res;
}
function reverse(linklist, k) {
const stack = [];
let current = linklist;
// 前面k个入栈
while (current.next && stack.length + 1 <= k) {
stack.push(current.value);
current = current.next;
}
// 不足k不用反转
if (stack.length < k) {
return linklist;
}
// 出栈+拼接current节点再递归
let temp = {};
const ret = stack.reduceRight(
(res, cur) => ((temp.value = cur), (temp = temp.next = {}), res),
temp
);
current && current.next && Object.assign(temp, reverse(current, k));
return ret;
}
reverse(createLinkList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), 3);
看了一楼的解释，我的理解是3-2-1,6-5-4,7-8，三组，难道我理解错了?
对啊，但是我写的是网络上头条的给的题目，头条是链表尾部开始，这个题目是表头开始，原理是类似的
class Node {
constructor(v, last) {
this.value = v
this.next = null
}
}
function NodeList() {
// 容器
let head = null
// 长度
let length = null
this.append = function(val) {
let cur,
node = new Node(val)
if (head == null) {
head = node
} else {
cur = head
while (cur.next) {
cur = cur.next
}
cur.next = node
}
length++
}
this.removeAt = function(pos) {
let cur = head,
index = 0,
prev
if (pos === 0) {
let nodes = cur
head = cur.next
return nodes
} else {
while (cur.next) {
if (index++ === pos) {
prev.next = cur.next
return cur
}
prev = cur
cur = cur.next
}
return -1
}
}
this.reverseList = function(k) {
let res
if (k >= length) {
return head
}
// 进行轮询节点反转
for (let i = 0; i < Math.floor(length / k) + 1; i++) {
let index = 0,
reverNodes
// 反转节点
while (index < k && head) {
// 拿到删除的节点（永远是第一个）
let node = nodeList.removeAt(0)
// 如果本轮节点组为空，则重置本次节点
if (reverNodes == null) {
reverNodes = node
node.next = null
} else {
// 拼接节点
node.next = reverNodes
reverNodes = node
}
index++
}
if (res == null) {
res = reverNodes
} else {
let cur = res
while (cur.next) {
cur = cur.next
}
cur.next = reverNodes
}
}
head = res
return res
}
this.getContent = function() {
let cur = head,
res = []
while (cur) {
res.push(cur.value)
cur = cur.next
}
console.log(res.join('->'))
return res.join('->')
}
}
// 实例节点
let nodeList = new NodeList()
// 添加节点
for (let i = 0; i < 20; i++) {
nodeList.append(i)
}
// 反转节点
nodeList.reverseList(3)
// 查看内容
nodeList.getContent()
数组犯规么，好吧那就不用数组，直接递归。
// 反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序
// 构建链表
function list(...val) {
let obj = val.reverse().map((res, i) => Object.assign({}, { [i]: new Node(res) }));
for (let item in obj) {
if (item != 0) obj[item][item].next = obj[Number(item) - 1][Number(item) - 1]
}
return obj[obj.length - 1][obj.length - 1];
};
class Node {
constructor(element) {
this.value = element;
this.next = null;
}
}
// 链表反转
function reverse_linkedList(linkedList) {
let str = '';
let fn = function (list) {
if (n === 1) {
if (list.next && list.next.next) {
let value = list.value;
let endValue = list.next.next.value;
list.next.next.value = value;
list.value = endValue;
}
}
str += list.value.toString() + ">"
if (n === 3) {
n = 0
}
if (list.next === null) {
return false
};
n++
fn(list.next)
return str.substring(0, str.length - 1)
}
return fn.call(reverse_linkedList, linkedList, n = 1)
}
let linkedList = list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
console.log("原始链表", list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
reverse_linkedList(linkedList);
console.log("\n反转链表", linkedList);
翻转链表一直都是热门题目，笔者就在某大型互联网公司的面试题中碰到过这种题目，这种题目很常常见，相对应的变形和扩展也很多，今天我们就来攻克它吧。
反转链表
反转链表是这个系列中最简单的了，没有别的要求，就是将一个链表从头到尾进行反转，最后返回反转后的链表即可。
我们来看一个 LeetCode 题目, 206. 反转链表, 官方难度为 Easy。
题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路
链表的翻转过程，初始化一个为 null 的 previous node（prev），然后遍历链表的同时，当前 node （curr）的下一个（next）指向前一个 node（prev）， 在改变当前 node 的指向之前，用一个临时变量记录当前 node 的下一个 node（curr.next). 即
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
举例如图：翻转整个链表 1->2->3->4->null -> 4->3->2->1->null
代码
我们直接来看下代码：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
if (!head || !head.next) return head;
let cur = head;
let pre = null;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
这里不再赘述，如果不理解，想看更多更详细内容，请参考我的LeetCode 题解 - 206.reverse-linked-list
分组反转
这个题目和上面的有点类似，只不过我们并不是从头到尾反转，而是每 k 个为一组进行反转。LeetCode 同样有原题25. K 个一组翻转链表官方难度为 Hard。
题目描述
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
我们的思路还是一样的，我们把每 k 位的位置当成是尾节点即可。 我们的任务就是每次反转头尾之间的所有节点，
然后将链表重新拼起来即可。 我们先来写一下反转头尾之间的所有节点这个方法。
// 翻转head到tail之间的部分，不包括head和tail
// 返回原链表的第一个元素，也就是翻转后的最后一个元素
function reverseList(head, tail) {
if (head === null || head.next === null) return head;
let cur = head.next;
first = cur;
let pre = head; // 这里就是翻转不包括head的原因，否则就是head.pre了（当然我们没有pre指针）
// 这里就是翻转不包括tail的原因，否则就是tail.next了。
while (cur !== tail) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 拼接
head.next = pre;
first.next = cur;
return first;
}
这里的反转不包括 head 和 tail，并不是我一开始的思路，但是在慢慢想的过程，发现这样写代码会更优雅。
上面的代码如果是 head 是我们的头节点，tail 是 null，那么就等效于上面的那道题。也就是说我们的这个 k 分组是上面题目的一般形式，当 k 为链表长度的时候，就会变成上面那道题了。
还有一点不同的是，我们每次反转之后都要对链表进行拼接，这是上面那个反转所没有的，这里要注意一下。
head.next = pre;
first.next = cur;
这里是对每一组（k个nodes）进行翻转，
-
先分组，用一个
count变量记录当前节点的个数 -
用一个
start变量记录当前分组的起始节点位置的前一个节点 -
用一个
end变量记录要翻转的最后一个节点位置 -
翻转一组（
k个nodes）即(start, end) - start and end exclusively。 -
翻转后，
start指向翻转后链表, 区间（start，end）中的最后一个节点, 返回start节点。 -
如果不需要翻转，
end就往后移动一个（end=end.next)，每一次移动，都要count+1.
如图所示 步骤 4 和 5： 翻转区间链表区间（start， end）
举例如图，head=[1,2,3,4,5,6,7,8], k = 3
NOTE: 一般情况下对链表的操作，都有可能会引入一个新的
dummy node，因为head有可能会改变。这里head 从1->3,dummy (List(0))保持不变。
这种做法的时间复杂度为 O(n)，空间复杂度为 O(1)。
代码
Java 代码：
class ReverseKGroupsLinkedList {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode start = dummy;
ListNode end = head;
int count = 0;
while (end != null) {
count++;
// group
if (count % k == 0) {
// reverse linked list (start, end]
start = reverse(start, end.next);
end = start.next;
} else {
end = end.next;
}
}
return dummy.next;
}
/**
* reverse linked list from range (start, end), return last node.
* for example:
* 0->1->2->3->4->5->6->7->8
* | |
* start end
*
* After call start = reverse(start, end)
*
* 0->3->2->1->4->5->6->7->8
* | |
* start end
* first
*
*/
private ListNode reverse(ListNode start, ListNode end) {
ListNode curr = start.next;
ListNode prev = start;
ListNode first = curr;
while (curr != end){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
start.next = prev;
first.next = curr;
return first;
}
}
Python3 代码：
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head is None or k < 2:
return head
dummy = ListNode(0)
dummy.next = head
start = dummy
end = head
count = 0
while end:
count += 1
if count % k == 0:
start = self.reverse(start, end.next)
end = start.next
else:
end = end.next
return dummy.next
def reverse(self, start, end):
prev, curr = start, start.next
first = curr
while curr != end:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
start.next = prev
first.next = curr
return first
JavaScript 代码：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
// 翻转head到tail之间的部分，不包括head和tail
// 返回原链表的第一个元素，也就是翻转后的最后一个元素
function reverseList(head, tail) {
if (head === null || head.next === null) return head;
let cur = head.next;
first = cur;
let pre = head; // 这里就是翻转不包括head的原因
while (cur !== tail) {
// 这里就是翻转不包括tail的原因
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 拼接
head.next = pre;
first.next = cur;
return first;
}
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if (head === null || k === 1) {
return head;
}
let cnt = 0;
const dummy = {
next: head,
};
let start = dummy;
let end = head;
while (end !== null) {
cnt++;
if (cnt % k !== 0) {
end = end.next;
} else {
start = reverseList(start, end.next);
end = start.next;
}
}
return dummy.next;
};
这里不再赘述，如果不理解，想看更多更详细内容，请参考我的LeetCode 题解 - 25.reverse-nodes-in-k-groups-cn
分组反转 - 增强版
这道题目来自字节跳动面试题。
题目描述
要求从后往前以k个为一组进行翻转。
例子，1->2->3->4->5->6->7->8, k = 3,
从后往前以k=3为一组，
6->7->8 为一组翻转为8->7->6， 3->4->5为一组翻转为5->4->3. 1->2只有2个nodes少于k=3个，不翻转。 最后返回： 1->2->5->4->3->8->7->6
思路
这里的思路跟从前往后以k个为一组进行翻转类似，可以进行预处理：
-
翻转链表
-
对翻转后的链表进行从前往后以k为一组翻转。
-
翻转步骤2中得到的链表。
例子：1->2->3->4->5->6->7->8, k = 3
-
翻转链表得到：
8->7->6->5->4->3->2->1 -
以k为一组翻转：
6->7->8->3->4->5->2->1 -
翻转步骤#2链表：
1->2->5->4->3->8->7->6
类似题目
var reverseKGroup = function(head, k) {
var curr = head;
var cnt = 0;
while (curr != null && cnt != k) {
curr = curr.next;
cnt++;
}
if (cnt == k) { // 如果足够 k 个元素，则翻转，否则返回
curr = reverseKGroup(curr, k); // 将后面的元素递归翻转
var newHead = curr;
while (cnt != 0) { // 翻转这一组的 k 个元素
var next = head.next;
head.next = newHead;
newHead = head;
head = next;
cnt--;
}
head = newHead;
}
return head;
};
type ListNodes = {
val?: number,
new_next?: ListNodes | null,
next?: ListNodes | null
}
function listReverse(list: ListNodes, k: number): ListNodes {
let result: ListNodes = {}
let prevNode: ListNodes = null
let connector: ListNodes = null
let to_be_connector: ListNodes = null
let count: number = 1
let is_first_flag = true
while (list !== null) {
list.new_next = prevNode
if (count === 1) {
if (is_first_flag) {
connector = list
} else {
to_be_connector = list
}
list.new_next = null
}
prevNode = list
if (count === k) {
count = 1
if (is_first_flag) {
result.new_next = list
is_first_flag = !is_first_flag
} else {
connector.new_next = list
connector = to_be_connector
}
} else {
count ++
}
list = list.next
}
if (count < k) {
connector.new_next = to_be_connector
while (to_be_connector !== null) {
to_be_connector.new_next = to_be_connector.next
to_be_connector = to_be_connector.next
}
}
return result.new_next
}
const l: ListNodes = {
val: 1,
next: {
val: 2,
next: {
val: 3,
next: {
val: 4,
next: {
val: 5,
next: {
val: 6,
next: {
val: 7,
next: {
val: 8,
next: {
val: 9,
next: {
val: 10,
next: null
}
}
}
}
}
}
}
}
}
}
console.log(listReverse(l, 4))
var result = [];
function reverseK(list, k){
var length = list.length;
if(length >= k){
var preK = list.slice(0, k).reverse();
var nextK = list.slice(k);
result.push(...preK)
reverseK(nextK, k)
}else{
result.push(...list)
}
return result;
}
var kk = reverseK([1,2,3,4,5,6,7,8], 3) // [3,2,1, 6,5,4,7,8]
console.log(kk)
var reverseKGroup = function(head, k) {
if (!head) return head
let fast = head
let i = k
// 一. 判断是否够长
while (i--) {
if (fast) {
fast = fast.next
} else {
return head
}
}
// 二. 够长就翻转当前的k段
let j = k
let node = head
let rev = null
while (j--) {
let temp = node.next
node.next = rev
rev = node
node = temp
}
// 三. 递归
head.next = reverseKGroup(node, k)
return rev
};
var reverseKGroup = function(head, k) { if (!head) return head let fast = head let i = k // 一. 判断是否够长 while (i--) { if (fast) { fast = fast.next } else { return head } } // 二. 够长就翻转当前的k段 let j = k let node = head let rev = null while (j--) { let temp = node.next node.next = rev rev = node node = temp } // 三. 递归 head.next = reverseKGroup(node, k) return rev };
不递归的写法
var reverseKGroup = function(head, k) {
let reverseList = []
let current = null
let end = null
let result = null
while(head){
if(reverseList.length < k){
reverseList.push(head.val)
}
if(reverseList.length == k){
while(reverseList.length>0){
current = new ListNode(reverseList.pop())
if(!end){
end = current
}else{
end.next = current
end = current
}
if(!result){
result = current
}
}
}
head = head.next
}
while(reverseList.length>0){
current = new ListNode(reverseList.shift())
if(!end){
end = current
}else{
end.next = current
end = current
}
if(!result){
result = current
}
}
return result
};
每隔 K 个就 reverse 一次，不足k就返回
function reverseKGroup(head, k) {
let a = head;
let b = head;
while (k-- > 0) {
if (!b) {
return head;
}
b = b.next;
}
let newHead = reverse(a, b);
a.next = reverseKGroup(b, k);
return newHead;
}
function reverse(a, b) {
let cur = a;
let res = null;
while (a !== b) {
const next = cur.next;
cur.next = res;
res = cur;
cur = next;
}
return res;
}
