The title

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code


The known node

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
Copy the code


Method one:

  • Define an empty front node
  • Define an iterated pointer to the head node
  • Iterate over the iteration pointer to back up the next node of the current node
  • Point next of the current node to the previous node you just defined
  • Move the former node to the current node and the current node to the next node
  • Finally, the pointer to the former node is returned

Code:

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
  let pre = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  return pre;
};
Copy the code

Method 2:

Recursion, each time only the current node pointing to the relationship is reversed.

Code:

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
  if (head === null || head.next == null) {
    return head;
  }

  let next = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return next;
};
Copy the code