Press "Enter" to skip to content

Posts tagged as “list”

花花酱 LeetCode 61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution: Find the prev of the new head

Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N

Time complexity: O(n) n is the length of the list
Space complexity: O(1)

C++

Java

Python3

花花酱 LeetCode 1367. Linked List in Binary Tree

Given a binary tree root and a linked list with head as the first node. 

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.  

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

  • 1 <= node.val <= 100 for each node in the linked list and binary tree.
  • The given linked list will contain between 1 and 100 nodes.
  • The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

花花酱 LeetCode 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Time complexity: O(max(n,m))
Space complexity: O(max(n,m))

C++

Java

Python3

花花酱 LeetCode 82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

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

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Solution:

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

C++

Related Problems

花花酱 LeetCode 83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

Solution:

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

C++