Posts tagged as “list”

花花酱 LeetCode 148. Sort List

By zxi on July 26, 2018

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

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

Example 2:

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

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

// Author: Huahua

// Running time: 32 ms

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

fast = fast->next->next;

slow = slow->next;

}

ListNode* mid = slow->next;

slow->next = nullptr; // Break the list.

return merge(sortList(head), sortList(mid));

}

private:

ListNode* merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 6 ms

class Solution {

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) return head;

ListNode slow = head;

ListNode fast = head.next;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

return merge(sortList(head), sortList(mid));

}

private ListNode merge(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val > l2.val) {

ListNode tmp = l1;

l1 = l2;

l2 = tmp;

}

tail.next = l1;

l1 = l1.next;

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

}

Python3

# Author: Huahua, 232 ms

class Solution:

def sortList(self, head):

def merge(l1, l2):

dummy = ListNode(0)

tail = dummy

while l1 and l2:

if l1.val > l2.val: l1, l2 = l2, l1

tail.next = l1

l1 = l1.next

tail = tail.next

tail.next = l1 if l1 else l2

return dummy.next

if not head or not head.next: return head

slow = head

fast = head.next

while fast and fast.next:

fast = fast.next.next

slow = slow.next

mid = slow.next

slow.next = None

return merge(self.sortList(head), self.sortList(mid))

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

int len = 1;

ListNode* cur = head;

while (cur = cur->next) ++len;

ListNode dummy(0);

dummy.next = head;

ListNode* l;

ListNode* r;

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next; // partial sorted head

tail = &dummy;

while (cur) {

l = cur;

r = split(l, n);

cur = split(r, n);

auto merged = merge(l, r);

tail->next = merged.first;

tail = merged.second;

}

return dummy.next;

}

private:

// Splits the list into two parts, first n element and the rest.

// Returns the head of the rest.

ListNode* split(ListNode* head, int n) {

while (--n && head)

head = head->next;

ListNode* rest = head ? head->next : nullptr;

if (head) head->next = nullptr;

return rest;

}

// Merges two lists, returns the head and tail of the merged list.

pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

while (tail->next) tail = tail->next;

return {dummy.next, tail};

}

};

花花酱 LeetCode 2. Add Two Numbers

By zxi on July 25, 2018

Problem

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

Simulate the addition, draw two numbers (one each) from l1, l2, if list is empty draw 0.

Using a dummy head makes things easier.

Time complexity: O(max(l1,l2))

Space complexity: O(max(l1,l2))

C++

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 30 ms

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

int sum = 0;

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null || l2 != null || sum != 0) {

if (l1 != null) {

sum += l1.val;

l1 = l1.next;

}

if (l2 != null) {

sum += l2.val;

l2 = l2.next;

}

tail.next = new ListNode(sum % 10);

sum /= 10;

tail = tail.next;

}

return dummy.next;

}

Python3

"""

Author: Huahua

Running time: 112 ms

"""

class Solution:

def addTwoNumbers(self, l1, l2):

s = 0

dummy = ListNode(0)

tail = dummy

while l1 or l2 or s > 0:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

tail.next = ListNode(s % 10)

s //= 10

tail = tail.next

return dummy.next

Problem

题目大意：给你一个链表，再给你一些合法的节点，问你链表中有多少个连通分量（所有节点必须合法）。

https://leetcode.com/problems/linked-list-components/description/

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000.
The value of each node in the linked list will be in the range [0, N - 1].
1 <= G.length <= 10000.
G is a subset of all values in the linked list.

Solution1: Graph Traversal using DFS

// Author: Huahua

// Running time: 76 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> f(G.begin(), G.end());

unordered_map<int, vector<int>> g;

int u = head->val;

while (head->next) {

head = head->next;

int v = head->val;

if (f.count(v) && f.count(u)) {

g[u].push_back(v);

g[v].push_back(u);

}

u = v;

}

int ans = 0;

unordered_set<int> visited;

for (int u : G) {

if (visited.count(u)) continue;

++ans;

dfs(u, g, visited);

}

return ans;

}

private:

void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) {

if (visited.count(cur)) return;

visited.insert(cur);

for (const int next : g[cur])

dfs(next, g, visited);

}

};

Solution 2: Count tail node in sub graph

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> g(G.begin(), G.end());

int ans = 0;

while (head) {

if (g.count(head->val) && (!head->next || !g.count(head->next->val)))

++ans;

head = head->next;

}

return ans;

}

};

Posts tagged as “list”

花花酱 LeetCode 876. Middle of the Linked List

Problem

Solution: Slow + Fast Pointers

花花酱 LeetCode 148. Sort List

Problem

Solution: Merge Sort

C++

Java

Python3

花花酱 LeetCode 2. Add Two Numbers

Problem

Solution: Simulation

C++

Java

Python3

Related Problems

花花酱 LeetCode 445. Add Two Numbers II

Problem

Solution: Simulation

Related Problems

花花酱 LeetCode 817. Linked List Components

Problem

Solution1: Graph Traversal using DFS

Solution 2: Count tail node in sub graph