我刚刚艰难地回答了一个简单的面试问题:请颠倒一个单链表。
虽然我没能及时提供一个有效的答案来挽救面试,但后来我还是想出了一个解决方案。
我的解决方案正确吗?你会如何与Big Oh分析这一点?是否有更有效的方法来反转单链表?
// reverse a linked list
var reverseLinkedList = function(linkedlist) {
var node = linkedlist;
var previous = null;
while(node) {
// reverse pointer
node.next = previous;
// increment previous to current node
previous = node;
// increment node to next node
if (node.next){
node = node.next
} else {
node = null;
}
}
}
注意:在搜索类似的帖子时,我确实在JavaScript中找到了一个例子。我想知道我的代码是否可行(没有temp
变量)。非常感谢。
您的代码有几个问题。这应该说明问题。
// reverse a linked list
var reverseLinkedList = function(linkedlist) {
var node = linkedlist;
var previous = null;
while(node) {
// save next or you lose it!!!
var save = node.next;
// reverse pointer
node.next = previous;
// increment previous to current node
previous = node;
// increment node to next node or null at end of list
node = save;
}
return previous; // Change the list head !!!
}
linkedlist = reverseLinkedList(linkedlist);
正如ckersch提到的,你可以在O(n)时间内递归地解决这个问题。问题是,您需要知道递归是内存密集型的,因为函数在调用堆栈中积累,直到它们达到停止条件并开始返回实际内容。
我解决这个问题的方法是:
const reverse = (head) => {
if (!head || !head.next) {
return head;
}
let temp = reverse(head.next);
head.next.next = head;
head.next = undefined;
return temp;
}
当reverse()到达列表的末尾时,它将获取最后一个节点作为新的头,并向后引用每个节点。
这在时间上是O(n),因为您在每个节点上都要执行恒定数量的操作。从概念上讲,没有比这更有效的方法了(就big-O表示法而言,可以进行一些代码优化。)
不能超过O(n)的原因是,为了做到这一点,您需要跳过一些节点。由于您需要修改每个节点,所以这是不可能的。
效率可以归结为一个常数。列表中每个项目可以执行的操作越少,代码执行的速度就越快。
我会这样实现:
function reverseLinkedList(list, previous){
//We need to use the the current setting of
//list.next before we change it. We could save it in a temp variable,
//or, we could call reverseLinkedList recursively
if(list.next !== null){
reverseLinkedList(list.next, list);
}
//Everything after 'list' is now reversed, so we don't need list.next anymore.
//We passed previous in as an argument, so we can go ahead and set next to that.
list.next = previous;
}
reverseLinkedList(list, null);
当然,这是递归的,所以在空间方面效率低下,但我喜欢递归代码:)
这也不会返回反向链表,但如果这很重要,我们可以很容易地修改内容。
ES6解决方案:只需跟踪反转的列表,并不断将其添加到tmp中。
const reverseLinkedList = (head) => {
let reversed = null;
while(head) {
const tmp = head;
head = head.next;
tmp.next = reversed;
reversed = tmp;
}
return reversed;
};
console.log(JSON.stringify(reverseLinkedList({
data: 1,
next: {
data: 2,
next: {
data: 3,
next: {
data: 4,
next: {
data: 5,
next: {
data: 5,
next: {
data: 6
}
}
}
}
}
}
})));
反转SinglyLinkedList:输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL
为了理解"解决方案",我们必须跟踪以前的头和下一个变量例如在上面的输入Head=1中;next=2我们没有previor,所以假设previor为null循环列表,直到head不为空。颠倒头部的连接(上一个和下一个)。以下是代码
var reverseList = function(head) {
let previous = null;
while(head !== null){
let next = head.next;
head.next = previous;
previous= head
head = next;
}
return previous;
};
//O(n) | O(1) wherre n is the number of nodes in the linked list
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
function reverseLinkedList(head) {
if(!head) return null;
let p1 = head;
let p2 = null;
while(p1){
let temp = p1.next;
p1.next = p2;
p2 = p1;
p1 = temp;
}
return p2;
}
const a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3)
console.log("Current Node",a);
console.log("Reversed List",reverseLinkedList(a))
class LinkedList {
constructor () {
this.head = this.tail = null
}
// add to the end of the list
append (value) {
if (!this.tail) {
this.head = this.tail = new Node(value)
} else {
let oldTail = this.head
this.head = new Node(value)
this.head.next = oldhead
}
}
reverseList() {
//your code here
let currentNode = this.head
this.head = null
while(currentNode) {
if (!this.head) {
this.head = new Node(currenthead.data)
} else {
let oldhead = this.head
this.head = new Node(currentNode.data)
this.head.next = oldhead
}
currentNode = currentNode.next
}
}
}
class Node {
constructor (value, next) {
this.data = value
this.next = next || null
}
}
const list = new LinkedList()
list.append(1)
list.append(2)
list.reverseList()
因为在链表的开头插入数据会将其他第一个节点推到最后,而且这是一个O(1)
过程。然后我创建了以下函数reverse()
它基本上在开头插入节点元素,这基本上会在结尾得到一个反向列表。
下面是一个演示:
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
insertFirst(data = null) {
// make new head point to the previous head
this.head = new Node(data, this.head);
this.size ++;
}
insertLast(data = null) { // insert last in the beginning will be the first in the linked list
const node = new Node(data);
// If empty, insert first
if (!this.head) this.insertFirst(data);
else {
let current = this.head;
// while next is not null, continue
while (current.next)
current = current.next;
// eventually next is null, we want to set next here to the node we want to add
current.next = node;
}
this.size ++;
}
// print linked list
print() {
let current = this.head;
let output = "";
while (current) { // while current is not null, eventually it will be null
output += current.data + " => ";
current = current.next; // current jumping to the next node
}
output += "| NULL"; // ending
console.log(output);
return output;
}
reverse() {
if (!this.head) return; // if no head, do nothing
let current = this.head;
const linkedList = new LinkedList(); // create a new linked list
// don't worry, it will be garbage collected once this function ends since it's not a global variable
while (current) {
linkedList.insertFirst(current.data); // insert first at the beginning will be the end of the linked list at the end
current = current.next;
}
// assign current head to the reversed linked list head
this.head = linkedList.head;
}
}
const linkedList = new LinkedList();
// fill data as 100 -> 200 -> 300 -> 400
linkedList.insertLast(100);
linkedList.insertLast(200);
linkedList.insertLast(300);
linkedList.insertLast(400);
// To view results
const bodyElement = document.getElementsByTagName("body")[0];
bodyElement.innerHTML = `<p>Original Linked List: <b>${linkedList.print()}</b></p>`; // 100 200 300 400
linkedList.reverse();
bodyElement.innerHTML += `<p>Reversed Linked List: <b>${linkedList.print()}</b></p>`; // 400 300 200 100
b {
color: green;
}
<body></body>
总的来说,这个reverse()
函数的整个过程就是O(n)
。
希望这听起来很清楚,如果我错了,请纠正我。
这是我的递归解决方案:https://codesandbox.io/s/reverse-linked-list-tqh2tq?file=/src/index.js
let d = { me: "d" };
let c = { me: "c", next: d };
let b = { me: "b", next: c };
let a = { me: "a", next: b };
const reverseMe = (o) => {
let lastDude;
if (o.next.next) lastDude = reverseMe(o.next);
else lastDude = o.next;
o.next.next = o;
o.next = null;
return lastDude;
};
console.log("result", reverseMe(a));