在JavaScript中反转链表的策略

您的代码有几个问题。这应该说明问题。

// 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));