Valid Parentheses

Problem Statement

Given a string s containing just the characters '(', ')', '[', ']', '{' and '}', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of closing bracket.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

What to notice first

• Each closing bracket must match the most recent unmatched opening bracket of the same type.
• This ordering requirement is the key insight — it’s a perfect use case for a stack data structure.
• The stack approach is faster and more intuitive than alternatives.

Examples

Input	Valid?	Explanation
"()"	true	Simple pair of parentheses
"()[]{}"	true	Three different pairs, all properly closed
"(]"	false	Closing bracket does not match opening bracket
"([{}])"	true	Nested brackets in correct order
"([)]"	false	Brackets closed in wrong order (interleaved)
""	true	Empty string is valid
"("	false	Unclosed opening bracket
")"	false	Closing bracket with no opening

Constraints

• 0 <= s.length <= 10^4
• s consists of parentheses only: '(', ')', '[', ']', '{', '}'

Real-World Applications

Where this pattern appears

• Code editors and IDEs — auto-closing brackets, syntax highlighting, bracket matching
• Compilers and interpreters — validating syntax trees and nested structures
• HTML/XML parsing — checking that tags are properly opened and closed
• Mathematical expression evaluation — ensuring parentheses are balanced before parsing
• Text editors — validating nested delimiters in code and markup

Complexity Comparison

Approach	Time	Space	Intuition	Best When
Stack	O(n)	O(n)	Process left-to-right, match using memory	General case — fast and clear
Replace Loop	O(n²)	O(n)	Remove pairs repeatedly	Learning the concept, simple implementation

Which approach should you learn first?

• Pick Stack if you want the best all-around solution.
• Pick Replace Loop if you want to understand the concept through a brute-force lens.

Recommended

Stack

O(n) time · O(n) space

Intuitive

Replace Loop

O(n²) time · O(n) space

Approach 1: Stack (Recommended)

★ Recommended

Use a stack to track opening brackets. When you encounter a closing bracket, check if it matches the most recent opening bracket on the stack.

Key insight: The last opened bracket that hasn’t been closed yet must match the current closing bracket. This is exactly what a stack provides — last-in-first-out (LIFO) access.

⏱ Time O(n) Single pass 💾 Space O(n) Stack in worst case

Step-by-step Example

Input: s = "([{}])"

Step	Char	Stack (before)	Action	Stack (after)
1	(	[]	Opening bracket → push	['(']
2	[	['(']	Opening bracket → push	['(', '[']
3	{	['(', '[']	Opening bracket → push	['(', '[', '{']
4	}	['(', '[', '{']	Closing bracket → top is { → match! pop	['(', '[']
5	]	['(', '[']	Closing bracket → top is [ → match! pop	['(']
6	)	['(']	Closing bracket → top is ( → match! pop	[]
End	—	[]	Stack empty → valid ✓	—

Input: s = "([)]"

Step	Char	Stack (before)	Action	Result
1	(	[]	Opening bracket → push	['(']
2	[	['(']	Opening bracket → push	['(', '[']
3	)	['(', '[']	Closing bracket → top is [, but we see ) → no match! ✗	Invalid

Animated walkthrough

How the stack solution validates parentheses

Watch the stack grow and shrink as opening brackets are pushed and closing brackets are matched and popped.

Back Autoplay Next Reset

Step 1 of 7

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function validParenthesesStack(s):
    stack = []
    bracketMap = {'(': ')', '[': ']', '{': '}'}

    for char in s:
        if char is an opening bracket:
            stack.push(char)
        else:
            if stack is empty or bracketMap[stack.pop()] != char:
                return false

    return stack is empty

Solution Code

Python

valid_parentheses_stack.py

from typing import List


def valid_parentheses_stack(s: str) -> bool:
    """
    Check if parentheses are balanced using a stack.

    Approach: Use a stack to match closing brackets with opening brackets.
    - Push opening brackets onto the stack
    - For each closing bracket, check if it matches the top of the stack
    - At the end, the stack should be empty

    Time: O(n) - single pass through the string
    Space: O(n) - stack size in worst case (all opening brackets)
    """
    stack = []
    bracket_map = {'(': ')', '[': ']', '{': '}'}

    for char in s:
        if char in bracket_map:
            # Opening bracket - push to stack
            stack.append(char)
        else:
            # Closing bracket - check if it matches
            if not stack or bracket_map[stack.pop()] != char:
                return False

    # Stack should be empty (all brackets matched)
    return len(stack) == 0


if __name__ == "__main__":
    # Test cases
    print(valid_parentheses_stack("()"))  # True
    print(valid_parentheses_stack("()[]{}"))  # True
    print(valid_parentheses_stack("(]"))  # False
    print(valid_parentheses_stack("([])"))  # True
    print(valid_parentheses_stack("{[]}"))  # True
    print(valid_parentheses_stack(""))  # True
    print(valid_parentheses_stack("("))  # False
    print(valid_parentheses_stack(")"))  # False

C++

valid_parentheses_stack.cpp

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

bool validParenthesesStack(std::string s) {
    /**
     * Check if parentheses are balanced using a stack.
     *
     * Approach: Use a stack to match closing brackets with opening brackets.
     * - Push opening brackets onto the stack
     * - For each closing bracket, check if it matches the top of the stack
     * - At the end, the stack should be empty
     *
     * Time: O(n) - single pass through the string
     * Space: O(n) - stack size in worst case (all opening brackets)
     */
    std::stack<char> st;
    std::unordered_map<char, char> bracket_map = {
        {'(', ')'}, {'[', ']'}, {'{', '}'}
    };

    for (char c : s) {
        if (bracket_map.count(c)) {
            // Opening bracket - push to stack
            st.push(c);
        } else {
            // Closing bracket - check if it matches
            if (st.empty() || bracket_map[st.top()] != c) {
                return false;
            }
            st.pop();
        }
    }

    // Stack should be empty (all brackets matched)
    return st.empty();
}

int main() {
    // Test cases
    std::cout << validParenthesesStack("()") << std::endl;  // 1
    std::cout << validParenthesesStack("()[]{}") << std::endl;  // 1
    std::cout << validParenthesesStack("(]") << std::endl;  // 0
    std::cout << validParenthesesStack("([])") << std::endl;  // 1
    std::cout << validParenthesesStack("{[]}") << std::endl;  // 1
    std::cout << validParenthesesStack("") << std::endl;  // 1
    std::cout << validParenthesesStack("(") << std::endl;  // 0
    std::cout << validParenthesesStack(")") << std::endl;  // 0
    return 0;
}

Java

valid_parentheses_stack.java

import java.util.Stack;
import java.util.HashMap;

public class Main {
    /**
     * Check if parentheses are balanced using a stack.
     *
     * Approach: Use a stack to match closing brackets with opening brackets.
     * - Push opening brackets onto the stack
     * - For each closing bracket, check if it matches the top of the stack
     * - At the end, the stack should be empty
     *
     * Time: O(n) - single pass through the string
     * Space: O(n) - stack size in worst case (all opening brackets)
     */
    public static boolean validParenthesesStack(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put('(', ')');
        bracketMap.put('[', ']');
        bracketMap.put('{', '}');

        for (char c : s.toCharArray()) {
            if (bracketMap.containsKey(c)) {
                // Opening bracket - push to stack
                stack.push(c);
            } else {
                // Closing bracket - check if it matches
                if (stack.isEmpty() || bracketMap.get(stack.pop()) != c) {
                    return false;
                }
            }
        }

        // Stack should be empty (all brackets matched)
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(validParenthesesStack("()"));  // true
        System.out.println(validParenthesesStack("()[]{}"));  // true
        System.out.println(validParenthesesStack("(]"));  // false
        System.out.println(validParenthesesStack("([])"));  // true
        System.out.println(validParenthesesStack("{[]}"));  // true
        System.out.println(validParenthesesStack(""));  // true
        System.out.println(validParenthesesStack("("));  // false
        System.out.println(validParenthesesStack(")"));  // false
    }
}

JavaScript

valid_parentheses_stack.js

/**
 * Check if parentheses are balanced using a stack.
 *
 * Approach: Use a stack to match closing brackets with opening brackets.
 * - Push opening brackets onto the stack
 * - For each closing bracket, check if it matches the top of the stack
 * - At the end, the stack should be empty
 *
 * Time: O(n) - single pass through the string
 * Space: O(n) - stack size in worst case (all opening brackets)
 */
function validParenthesesStack(s) {
    const stack = [];
    const bracketMap = {
        '(': ')',
        '[': ']',
        '{': '}'
    };

    for (const char of s) {
        if (char in bracketMap) {
            // Opening bracket - push to stack
            stack.push(char);
        } else {
            // Closing bracket - check if it matches
            if (stack.length === 0 || bracketMap[stack.pop()] !== char) {
                return false;
            }
        }
    }

    // Stack should be empty (all brackets matched)
    return stack.length === 0;
}

// Test cases
console.log(validParenthesesStack("()"));  // true
console.log(validParenthesesStack("()[]{}"));  // true
console.log(validParenthesesStack("(]"));  // false
console.log(validParenthesesStack("([])"));  // true
console.log(validParenthesesStack("{[]}"));  // true
console.log(validParenthesesStack(""));  // true
console.log(validParenthesesStack("("));  // false
console.log(validParenthesesStack(")"));  // false

Rust

valid_parentheses_stack.rs

use std::collections::HashMap;

/**
 * Check if parentheses are balanced using a stack.
 *
 * Approach: Use a stack to match closing brackets with opening brackets.
 * - Push opening brackets onto the stack
 * - For each closing bracket, check if it matches the top of the stack
 * - At the end, the stack should be empty
 *
 * Time: O(n) - single pass through the string
 * Space: O(n) - stack size in worst case (all opening brackets)
 */
fn valid_parentheses_stack(s: &str) -> bool {
    let mut stack = Vec::new();
    let mut bracket_map = HashMap::new();
    bracket_map.insert('(', ')');
    bracket_map.insert('[', ']');
    bracket_map.insert('{', '}');

    for c in s.chars() {
        if bracket_map.contains_key(&c) {
            // Opening bracket - push to stack
            stack.push(c);
        } else {
            // Closing bracket - check if it matches
            if let Some(last) = stack.pop() {
                if bracket_map.get(&last) != Some(&c) {
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    // Stack should be empty (all brackets matched)
    stack.is_empty()
}

fn main() {
    // Test cases
    println!("{}", valid_parentheses_stack("()"));  // true
    println!("{}", valid_parentheses_stack("()[]{}"));  // true
    println!("{}", valid_parentheses_stack("(]"));  // false
    println!("{}", valid_parentheses_stack("([])"));  // true
    println!("{}", valid_parentheses_stack("{[]}"));  // true
    println!("{}", valid_parentheses_stack(""));  // true
    println!("{}", valid_parentheses_stack("("));  // false
    println!("{}", valid_parentheses_stack(")"));  // false
}

Go

valid_parentheses_stack.go

package main

import "fmt"

/**
 * Check if parentheses are balanced using a stack.
 *
 * Approach: Use a stack to match closing brackets with opening brackets.
 * - Push opening brackets onto the stack
 * - For each closing bracket, check if it matches the top of the stack
 * - At the end, the stack should be empty
 *
 * Time: O(n) - single pass through the string
 * Space: O(n) - stack size in worst case (all opening brackets)
 */
func validParenthesesStack(s string) bool {
  stack := make([]rune, 0)
  bracketMap := map[rune]rune{
    '(': ')',
    '[': ']',
    '{': '}',
  }

  for _, c := range s {
    if val, ok := bracketMap[c]; ok {
      // Opening bracket - push to stack
      stack = append(stack, c)
    } else {
      // Closing bracket - check if it matches
      if len(stack) == 0 || bracketMap[stack[len(stack)-1]] != c {
        return false
      }
      stack = stack[:len(stack)-1]
    }
  }

  // Stack should be empty (all brackets matched)
  return len(stack) == 0
}

func main() {
  // Test cases
  fmt.Println(validParenthesesStack("()"))        // true
  fmt.Println(validParenthesesStack("()[]{}"))    // true
  fmt.Println(validParenthesesStack("(]"))        // false
  fmt.Println(validParenthesesStack("([])"))      // true
  fmt.Println(validParenthesesStack("{[]}"))      // true
  fmt.Println(validParenthesesStack(""))          // true
  fmt.Println(validParenthesesStack("("))         // false
  fmt.Println(validParenthesesStack(")"))         // false
}

Approach 2: Replace Loop

✓ Simple

Repeatedly remove consecutive pairs of matching brackets until no more can be removed. If the string becomes empty, it is valid.

This approach is conceptually simpler but less efficient. It directly models the idea that valid brackets always have matching pairs next to each other.

Why this is slower

Each removal operation scans the entire remaining string. In the worst case (e.g., "((()))") you perform O(n) iterations, each taking O(n) time to remove pairs, giving O(n²) total time.

⏱ Time O(n²) Multiple passes 💾 Space O(n) Temporary strings

Step-by-step Example

Input: s = "([{}])"

Pass	Current String	Pairs Removed	Next String
1	"([{}])"	{}	"([])"
2	"([])"	[]	"()"
3	"()"	()	""
End	""	—	Valid ✓

Input: s = "([)]"

Pass	Current String	Pairs Removed	Next String
1	"([)]"	—	"([)]"
End	"([)]"	No pairs to remove	Invalid ✗

Pseudocode

function validParenthesesReplace(s):
    while s contains "()" or "[]" or "{}":
        remove all occurrences of "()", "[]", "{}"
    return s is empty

Solution Code

Python

valid_parentheses_replace.py

def valid_parentheses_replace(s: str) -> bool:
    """
    Check if parentheses are balanced by repeatedly removing matched pairs.

    Approach: Repeatedly remove consecutive pairs of matching brackets
    until either the string is empty (valid) or no more pairs can be removed (invalid).

    Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
    Space: O(n) - for temporary string during replacement

    Note: This approach is simple to understand but slower than stack.
    """
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "").replace("[]", "").replace("{}", "")

    return len(s) == 0


if __name__ == "__main__":
    # Test cases
    print(valid_parentheses_replace("()"))  # True
    print(valid_parentheses_replace("()[]{}"))  # True
    print(valid_parentheses_replace("(]"))  # False
    print(valid_parentheses_replace("([])"))  # True
    print(valid_parentheses_replace("{[]}"))  # True
    print(valid_parentheses_replace(""))  # True
    print(valid_parentheses_replace("("))  # False
    print(valid_parentheses_replace(")"))  # False

C++

valid_parentheses_replace.cpp

#include <iostream>
#include <string>

bool validParenthesesReplace(std::string s) {
    /**
     * Check if parentheses are balanced by repeatedly removing matched pairs.
     *
     * Approach: Repeatedly remove consecutive pairs of matching brackets
     * until either the string is empty (valid) or no more pairs can be removed (invalid).
     *
     * Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
     * Space: O(n) - for temporary strings during replacement
     *
     * Note: This approach is simple to understand but slower than stack.
     */
    bool changed = true;
    while (changed) {
        changed = false;
        size_t pos = 0;

        // Find and remove pairs
        while ((pos = s.find("()")) != std::string::npos) {
            s.erase(pos, 2);
            changed = true;
        }
        pos = 0;
        while ((pos = s.find("[]")) != std::string::npos) {
            s.erase(pos, 2);
            changed = true;
        }
        pos = 0;
        while ((pos = s.find("{}")) != std::string::npos) {
            s.erase(pos, 2);
            changed = true;
        }
    }

    return s.empty();
}

int main() {
    // Test cases
    std::cout << validParenthesesReplace("()") << std::endl;  // 1
    std::cout << validParenthesesReplace("()[]{}") << std::endl;  // 1
    std::cout << validParenthesesReplace("(]") << std::endl;  // 0
    std::cout << validParenthesesReplace("([])") << std::endl;  // 1
    std::cout << validParenthesesReplace("{[]}") << std::endl;  // 1
    std::cout << validParenthesesReplace("") << std::endl;  // 1
    std::cout << validParenthesesReplace("(") << std::endl;  // 0
    std::cout << validParenthesesReplace(")") << std::endl;  // 0
    return 0;
}

Java

valid_parentheses_replace.java

public class Main {
    /**
     * Check if parentheses are balanced by repeatedly removing matched pairs.
     *
     * Approach: Repeatedly remove consecutive pairs of matching brackets
     * until either the string is empty (valid) or no more pairs can be removed (invalid).
     *
     * Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
     * Space: O(n) - for temporary strings during replacement
     *
     * Note: This approach is simple to understand but slower than stack.
     */
    public static boolean validParenthesesReplace(String s) {
        String prev;
        do {
            prev = s;
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (!s.equals(prev));

        return s.length() == 0;
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(validParenthesesReplace("()"));  // true
        System.out.println(validParenthesesReplace("()[]{}"));  // true
        System.out.println(validParenthesesReplace("(]"));  // false
        System.out.println(validParenthesesReplace("([])"));  // true
        System.out.println(validParenthesesReplace("{[]}"));  // true
        System.out.println(validParenthesesReplace(""));  // true
        System.out.println(validParenthesesReplace("("));  // false
        System.out.println(validParenthesesReplace(")"));  // false
    }
}

JavaScript

valid_parentheses_replace.js

/**
 * Check if parentheses are balanced by repeatedly removing matched pairs.
 *
 * Approach: Repeatedly remove consecutive pairs of matching brackets
 * until either the string is empty (valid) or no more pairs can be removed (invalid).
 *
 * Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
 * Space: O(n) - for temporary strings during replacement
 *
 * Note: This approach is simple to understand but slower than stack.
 */
function validParenthesesReplace(s) {
    let prev;
    do {
        prev = s;
        s = s.replace(/\(\)/g, "").replace(/\[\]/g, "").replace(/\{\}/g, "");
    } while (s !== prev);

    return s.length === 0;
}

// Test cases
console.log(validParenthesesReplace("()"));  // true
console.log(validParenthesesReplace("()[]{}"));  // true
console.log(validParenthesesReplace("(]"));  // false
console.log(validParenthesesReplace("([])"));  // true
console.log(validParenthesesReplace("{[]}"));  // true
console.log(validParenthesesReplace(""));  // true
console.log(validParenthesesReplace("("));  // false
console.log(validParenthesesReplace(")"));  // false

Rust

valid_parentheses_replace.rs

/**
 * Check if parentheses are balanced by repeatedly removing matched pairs.
 *
 * Approach: Repeatedly remove consecutive pairs of matching brackets
 * until either the string is empty (valid) or no more pairs can be removed (invalid).
 *
 * Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
 * Space: O(n) - for temporary strings during replacement
 *
 * Note: This approach is simple to understand but slower than stack.
 */
fn valid_parentheses_replace(mut s: String) -> bool {
    let mut prev;
    loop {
        prev = s.clone();
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
        if s == prev {
            break;
        }
    }

    s.is_empty()
}

fn main() {
    // Test cases
    println!("{}", valid_parentheses_replace("()".to_string()));  // true
    println!("{}", valid_parentheses_replace("()[]{}".to_string()));  // true
    println!("{}", valid_parentheses_replace("(]".to_string()));  // false
    println!("{}", valid_parentheses_replace("([])".to_string()));  // true
    println!("{}", valid_parentheses_replace("{[]}".to_string()));  // true
    println!("{}", valid_parentheses_replace("".to_string()));  // true
    println!("{}", valid_parentheses_replace("(".to_string()));  // false
    println!("{}", valid_parentheses_replace(")".to_string()));  // false
}

Go

valid_parentheses_replace.go

package main

import (
  "fmt"
  "strings"
)

/**
 * Check if parentheses are balanced by repeatedly removing matched pairs.
 *
 * Approach: Repeatedly remove consecutive pairs of matching brackets
 * until either the string is empty (valid) or no more pairs can be removed (invalid).
 *
 * Time: O(n²) - each pass removes at least 2 characters, up to n/2 passes
 * Space: O(n) - for temporary strings during replacement
 *
 * Note: This approach is simple to understand but slower than stack.
 */
func validParenthesesReplace(s string) bool {
  prev := ""
  for s != prev {
    prev = s
    s = strings.ReplaceAll(s, "()", "")
    s = strings.ReplaceAll(s, "[]", "")
    s = strings.ReplaceAll(s, "{}", "")
  }

  return len(s) == 0
}

func main() {
  // Test cases
  fmt.Println(validParenthesesReplace("()"))        // true
  fmt.Println(validParenthesesReplace("()[]{}"))    // true
  fmt.Println(validParenthesesReplace("(]"))        // false
  fmt.Println(validParenthesesReplace("([])"))      // true
  fmt.Println(validParenthesesReplace("{[]}"))      // true
  fmt.Println(validParenthesesReplace(""))          // true
  fmt.Println(validParenthesesReplace("("))         // false
  fmt.Println(validParenthesesReplace(")"))         // false
}

Common mistakes

Watch for these pitfalls

• Forgetting to check if the stack is empty before popping when encountering a closing bracket. A closing bracket with no matching opening bracket should return false immediately.
• Wrong bracket type match — "(]" should return false because the closing bracket type does not match the opening bracket type.
• Forgetting the final check — even if you match all closing brackets, you must ensure the stack is empty (no unmatched opening brackets remain).
• Checking stack non-empty after the loop — common mistake: only checking stack.empty() but never validating matches during iteration.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

valid_parentheses_space_optimized.py

"""
Solution for Valid Parentheses
"""

def solve():
    """Implementation for approach 3 of Valid Parentheses"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

valid_parentheses_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Valid Parentheses
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ValidParenthesesSpaceOptimized.java

/**
 * Solution for Valid Parentheses
 * Approach 3
 */
public class ValidParenthesesSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

valid_parentheses_space_optimized.js

/**
 * Solution for Valid Parentheses
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

valid_parentheses_space_optimized.rs

/// Solution for Valid Parentheses
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

valid_parentheses_space_optimized.go

package main

import "fmt"

// Solution for Valid Parentheses
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Longest Valid Parentheses ↗ Hard #32
• Valid Sudoku ↗ Medium #36
• Evaluate Reverse Polish Notation ↗ Medium #150
• Min Stack ↗ Medium #155

Interview Tips

Key discussion points

• Why stack over brute force? Stack processes the string in a single pass. The replace loop must repeatedly scan and modify the string, making it quadratic.
• Follow-up: Generate parentheses — given n pairs, generate all valid combinations. This requires backtracking and builds on the validation concept.
• Follow-up: Longest valid parentheses — find the longest substring of valid parentheses. This uses dynamic programming or stack with index tracking.
• Edge cases to mention: empty string (valid), single character (invalid), all opening brackets, all closing brackets, alternating mismatched types like "(][)]".
• Time vs. space trade-off: Stack approach uses linear space to achieve linear time. There’s no way to do this in O(1) space without exponential time.

← Previous
#19 Remove Nth Node From End of List Next
#21 Merge Two Sorted Lists →