Skip to content

linkedList.md

Latest commit

 

History

History
75 lines (49 loc) · 3.24 KB

linkedList.md

File metadata and controls

75 lines (49 loc) · 3.24 KB
Raw

Linked List

  1. Implement Linked List
  2. Add two numbers

Linked List

Description

[Medium] Linked list is a linear collection of data elements. Each node contains a value and a reference to the next node.

Comparison with array:

  1. Memory allocation. Array uses contiguous memory allocation, meaning all elements are stored next to each other in memory. Linked list uses dynamic memory allocation, where each node is stored in different locations and linked via pointers.
  2. Insertion & Deletion. Array requires shifting elements; its time complexity is O(n). Linked list offers more efficient insertion and deletion; its time complexity is O(1).
  3. Accessing. Array is more efficient in accessing elements using an index. Its time complexity is O(1). Linked list needs to traverse to access a particular value. Its time complexity is O(n).

Implement linked list data structure and relevant methods:

  • size() Get the length of linked list.
  • getFirst() Get the first node of linked list.
  • getLast() Get the last node of linked list.
  • getAt(index) Get the node at given index.
  • search(value) Search for the node with the given value.
  • insertFirst(value) Insert a node to the top of linked list.
  • insertLast(value) Append a node to the end of linked list.
  • insertAt(value, index) Insert a node at the given index.
  • removeFirst() Remove the first node from linked list.
  • removeLast() Remove the last node from linked list.
  • removeAt(index) Remove the node at given index.
  • clear() Clear linked list.

Implementation

Back to index

Add Two Numbers

Leetcode-2

Description

[Medium] Given two non-empty linked list representing positive integers, the digits are stored in reverse order and each of the nodes contains a single digit. Add the two numbers and return the sum as a linked list.

Example

l1: 2 -> 5 -> 3, l2: 5 -> 6 -> 4 -> sum: 7 -> 1 -> 8 ( 352 + 465 = 817 )

l1: 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9, l2: 9 -> 9 -> 9 -> 9 -> sum: 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 ( 9999999 + 9999 = 10009998 )

Solution

Create an empty linked list to store the sum.

Use two pointers to traverse the reversed lists simultaneously. For each pair of nodes, compute their sum and if the sum exceeds 9, store the remainder(sum modulo 10) in the new node and forward the carry to the next pair of nodes. Append each new node to result.

Continue until both lists are fully traversed, handling any remaining nodes from the longer list and carrying over any final carry.

Implementation

Back to index