Solution 1 - Iterative Pointer Traversal

Traverse the sorted linked list with a pointer. At each node, if the next node has the same value, skip it by updating the next pointer. Otherwise, move to the next node. Since the list is sorted, all duplicates are adjacent.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Remove Duplicates from Sorted List Function"""
        curr = head

        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return head


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def to_list(head):
    """Helper to collect list values"""
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def testcase():
    """Test Function"""
    print(to_list(Solution().deleteDuplicates(build_list([1, 1, 2]))))  # [1, 2]
    print(to_list(Solution().deleteDuplicates(build_list([1, 1, 2, 3, 3]))))  # [1, 2, 3]
    print(to_list(Solution().deleteDuplicates(build_list([]))))  # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    /** Remove Duplicates from Sorted List Function */
    deleteDuplicates(head) {
        let curr = head;

        while (curr && curr.next) {
            if (curr.val === curr.next.val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return head;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function buildList(vals) {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function toList(head) {
    const out = [];
    while (head) {
        out.push(head.val);
        head = head.next;
    }
    return out;
}

function testcase() {
    const solution = new Solution();
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2]))));
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2, 3, 3]))));
    console.log(toList(solution.deleteDuplicates(buildList([]))));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
    constructor(public val: number = 0, public next: ListNode | null = null) {}
}

class Solution {
    /** Remove Duplicates from Sorted List Function */
    deleteDuplicates(head: ListNode | null): ListNode | null {
        let curr: ListNode | null = head;

        while (curr && curr.next) {
            if (curr.val === curr.next.val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return head;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function buildList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur: ListNode = dummy;
    for (const v of vals) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) {
        out.push(head.val);
        head = head.next;
    }
    return out;
}

function testcase(): void {
    const solution = new Solution();
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2]))));
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2, 3, 3]))));
    console.log(toList(solution.deleteDuplicates(buildList([]))));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type ListNode struct {
	Val  int
	Next *ListNode
}

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func deleteDuplicates(head *ListNode) *ListNode {
	curr := head

	for curr != nil && curr.Next != nil {
		if curr.Val == curr.Next.Val {
			curr.Next = curr.Next.Next
		} else {
			curr = curr.Next
		}
	}
	return head
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func toSlice(head *ListNode) []int {
	out := []int{}
	for head != nil {
		out = append(out, head.Val)
		head = head.Next
	}
	return out
}

func testcase() {
	fmt.Println(toSlice(deleteDuplicates(buildList([]int{1, 1, 2}))))
	fmt.Println(toSlice(deleteDuplicates(buildList([]int{1, 1, 2, 3, 3}))))
	fmt.Println(toSlice(deleteDuplicates(buildList([]int{}))))
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0083.1 - Remove Duplicates from Sorted List - Solution 1 - Iterative Pointer Traversal

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

struct Solution;

impl Solution {
    /// Remove Duplicates from Sorted List Function
    pub fn delete_duplicates(head: &mut Option<Box<ListNode>>) {
        let mut curr = head.as_mut();

        while let Some(node) = curr {
            let mut next = node.next.as_mut();
            while let Some(n) = next {
                if n.val == node.val {
                    node.next = n.next.take();
                    next = node.next.as_mut();
                } else {
                    break;
                }
            }
            curr = node.next.as_mut();
        }
    }
}

fn main() {
    let mut head = Some(Box::new(ListNode::new(1)));
    Solution::delete_duplicates(&mut head);
    println!("{:?}", head);
}

Solution 2 - Recursive Approach

Recursively process the list. For each node, recursively remove duplicates from the rest of the list. If the current node's value equals the next node's value, skip the current node by returning head.next. Otherwise, return the current node.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Remove Duplicates from Sorted List Function"""
        if not head or not head.next:
            return head

        head.next = self.deleteDuplicates(head.next)

        return head.next if head.val == head.next.val else head


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def to_list(head):
    """Helper to collect list values"""
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def testcase():
    """Test Function"""
    print(to_list(Solution().deleteDuplicates(build_list([1, 1, 2]))))  # [1, 2]
    print(to_list(Solution().deleteDuplicates(build_list([1, 1, 2, 3, 3]))))  # [1, 2, 3]
    print(to_list(Solution().deleteDuplicates(build_list([]))))  # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    /** Remove Duplicates from Sorted List Function */
    deleteDuplicates(head) {
        if (!head || !head.next) return head;

        head.next = this.deleteDuplicates(head.next);
        return head.next && head.val === head.next.val ? head.next : head;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function buildList(vals) {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function toList(head) {
    const out = [];
    while (head) {
        out.push(head.val);
        head = head.next;
    }
    return out;
}

function testcase() {
    const solution = new Solution();
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2]))));
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2, 3, 3]))));
    console.log(toList(solution.deleteDuplicates(buildList([]))));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
    constructor(public val: number = 0, public next: ListNode | null = null) {}
}

class Solution {
    /** Remove Duplicates from Sorted List Function */
    deleteDuplicates(head: ListNode | null): ListNode | null {
        if (!head || !head.next) return head;

        head.next = this.deleteDuplicates(head.next);
        return head.next && head.val === head.next.val ? head.next : head;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function buildList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur: ListNode = dummy;
    for (const v of vals) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) {
        out.push(head.val);
        head = head.next;
    }
    return out;
}

function testcase(): void {
    const solution = new Solution();
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2]))));
    console.log(toList(solution.deleteDuplicates(buildList([1, 1, 2, 3, 3]))));
    console.log(toList(solution.deleteDuplicates(buildList([]))));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type ListNode struct {
	Val  int
	Next *ListNode
}

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func deleteDuplicatesRecursive(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	head.Next = deleteDuplicatesRecursive(head.Next)
	if head.Next != nil && head.Val == head.Next.Val {
		return head.Next
	}
	return head
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func toSlice(head *ListNode) []int {
	out := []int{}
	for head != nil {
		out = append(out, head.Val)
		head = head.Next
	}
	return out
}

func testcase() {
	fmt.Println(toSlice(deleteDuplicatesRecursive(buildList([]int{1, 1, 2}))))
	fmt.Println(toSlice(deleteDuplicatesRecursive(buildList([]int{1, 1, 2, 3, 3}))))
	fmt.Println(toSlice(deleteDuplicatesRecursive(buildList([]int{}))))
}

/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0083.2 - Remove Duplicates from Sorted List - Solution 2 - Recursive Approach

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

struct Solution;

impl Solution {
    pub fn delete_duplicates(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head.as_mut() {
            None => head,
            Some(node) => {
                let next = Solution::delete_duplicates(node.next.take());
                node.next = next;

                if let Some(n) = node.next.as_ref() {
                    if n.val == node.val {
                        return node.next.take();
                    }
                }
                head
            }
        }
    }
}

fn main() {
    let head: Option<Box<ListNode>> = None;
    println!("{:?}", Solution::delete_duplicates(head));
}

0083 - Remove Duplicates from Sorted List

Solution 1 - Iterative Pointer Traversal

Solution 2 - Recursive Approach