206. Reverse Linked List

Problem

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution 1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  var newHead = null;
  var tmp = null;
  while (head) {
    tmp = head.next;
    head.next = newHead;
    newHead = head;
    head = tmp;
  }
  return newHead;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).

Solution 2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  return reverse(null, head);
};

var reverse = function (newHead, head) {
  if (!head) return newHead;
  var tmp = head.next;
  head.next = newHead;
  return reverse(head, tmp);
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).