第 138 题：反转链表，每 k 个节点反转一次，不足 k 就保持原有顺序 #278
Comments
|
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(); |
|
楼上的各位，这题用数组做就没意思了啊
// 定义链表节点
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); |
|
糟糕，又是不会的感觉 |
|
(#`O′)！你们用数组的不觉得很犯规么！ |
我记得看到头条的是说不能用其他的数据结构 |
|
我枯了 |
|
看了一楼的解释，我的理解是3-2-1,6-5-4,7-8，三组，难道我理解错了? |
对啊，但是我写的是网络上头条的给的题目，头条是链表尾部开始，这个题目是表头开始，原理是类似的 |
|
数组犯规么，好吧那就不用数组，直接递归。// 反转链表，每 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。 题目描述思路链表的翻转过程，初始化一个为 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 位的位置当成是尾节点即可。 我们的任务就是每次反转头尾之间的所有节点， // 翻转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;这里是对每一组（
如图所示 步骤 4 和 5： 翻转区间链表区间 举例如图，
这种做法的时间复杂度为 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 firstJavaScript 代码： /**
* 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， 思路这里的思路跟从前往后以
例子：
类似题目 |
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 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
}; |
不递归的写法 |
|
每隔 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;
} |
reverse 函数默认指针有问题，first.next = end 。应该才对，不然就是成环了 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No description provided.
The text was updated successfully, but these errors were encountered: