Grind75 Notes
  • README
  • week-1
    • Two Sum
    • Valid Parentheses
    • Merge Two Sorted Lists
    • Best Time to Buy and Sell Stock
    • Valid Palindrome
    • Invert Binary Tree
    • Valid Anagram
    • Binary Search
    • Flood Fill
    • Lowest Common Ancestor of a Binary Search Tree
    • Balanced Binary Tree
    • Linked List Cycle
    • Implement Queue using Stacks
  • week-2
    • First Bad Version
    • Ransom Note
    • Climbing Stairs
    • Longest Palindrome
    • Reverse Linked List
    • Majority Element
    • Add Binary
    • Diameter of Binary Tree
    • Middle of the Linked List
    • Maximum Depth of Binary Tree
    • Contains Duplicate
    • Maximum Subarray
  • week-3
    • Insert Interval
    • 01 Matrix
    • K Closest Points to Origin
    • Longest Substring Without Repeating Characters
    • 3Sum
    • Binary Tree Level Order Traversal
    • Clone Graph
    • Evaluate Reverse Polish Notation
  • week-4
    • Course Schedule
    • Implement Trie (Prefix Tree)
    • Coin Change
    • Product of Array Except Self
    • Min Stack
    • Validate Binary Search Tree
    • Number of Islands
    • Rotting Oranges
  • week-5
    • Search in Rotated Sorted Array
    • Combination Sum
    • Permutations
    • Merge Intervals
    • Lowest Common Ancestor of a Binary Tree
    • Time Based Key-Value Store
    • Accounts Merge
    • Sort Colors
  • week-6
    • Word Break
    • Partition Equal Subset Sum
    • String to Integer (atoi)
    • Spiral Matrix
    • Subsets
    • Binary Tree Right Side View
    • Longest Palindromic Substring
    • Unique Paths
    • Construct Binary Tree from Preorder and Inorder Traversal
  • week-7
    • Container With Most Water
    • Letter Combinations of a Phone Number
    • Word Search
    • Find All Anagrams in a String
    • Minimum Height Trees
    • Task Scheduler
    • LRU Cache
  • week-8
    • Kth Smallest Element in a BST
    • Minimum Window Substring
    • Serialize and Deserialize Binary Tree
    • Trapping Rain Water
    • Find Median from Data Stream
    • Word Ladder
    • Basic Calculator
    • Maximum Profit in Job Scheduling
    • Merge k Sorted Lists
    • Largest Rectangle in Histogram
Powered by GitBook
On this page
  • Problem
  • Pseudocode
  • Solution
  • Time and Space Complexity
  1. week-2

Reverse Linked List

PreviousLongest PalindromeNextMajority Element

Last updated 2 years ago

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Pseudocode

initial intuition is to replace node.val but without an array it's not possible to retrieve the first node val when recursing the last value
instead, just extend the last node, node.next to previous e.g.
1 -> 2 -> 3 -> 4 -> 5
                     5 -> 4 -> 3 -> 2 -> 1 
new reverse node is returned at the end of each recursion, adding the prev value to node.next. remember that objects are passed by reference

Solution

var reverseList = function (head) {
  return walk(head, null);
};

function walk(node, prev) {
  if (!node) {
    return prev;
  }

  const extend = walk(node.next, node);

  node.next = prev;

  return extend;
}

Time and Space Complexity

Time

  • Linked list has to be traversed to the end and reassigned next to previous - O(N)

  • Total - O(N)

Space

  • A reverse linked list was returned - O(N)

  • Total - O(N)

Loading...LeetCode
Logo