Chapter 9 Linked List

As a data structure, linked list can be considered as a one dimension, simplified, or flattened binary tree.

Related Algorithms:

  • Two pointers/ three pointers
  • Recursion

The algorithm idea is pretty much like array. The difficulty is mainly from the non-random-accessiblity of list node. The most error-prone part is connecting the node correctly!

链表操作基本技巧之一: reverse linked list

最后p就是新的head.

链表操作基本技巧之二: 找Lower Median,中点

最后slow就是中点.

链表操作基本技巧之三: delete a node

There are two kinds of delete: delete current node or next node

  • 删除当前元素(current node):
  1. p->next = c->next or c->val=c->next->val, c->next=c->next->next;
    这个方法有个缺点不能删除尾巴,所以要慎用.做这个题体会一下.
  • 删除下一个元素(next node):
  1. c->next=c->next->next

Leetcode Problems:

328     Odd Even Linked List            37.4%           Medium
237     Delete Node in a Linked List    43.6%           Easy
234     Palindrome Linked List          27.8%           Easy
206     Reverse Linked List             39.1%           Easy
203     Remove Linked List Elements     28.4%           Easy
160     Intersection of Two Linked Lists30.2%           Easy
148     Sort List                       24.6%           Medium
147     Insertion Sort List             29.1%           Medium
143     Reorder List                    22.6%           Medium
142     Linked List Cycle II            31.5%           Medium
141     Linked List Cycle               36.9%           Medium
138     Copy List with Random Pointer   26.0%           Hard
114     Flatten Binary Tree to Linked List              30.9%           Medium
109     Convert Sorted List to Binary Search Tree       30.2%           Medium
92      Reverse Linked List II                          27.7%           Medium
86      Partition List                                  29.3%           Medium
83      Remove Duplicates from Sorted List              36.6%           Easy
82      Remove Duplicates from Sorted List II           26.8%           Medium
61      Rotate List                                     22.8%           Medium
23      Merge k Sorted Lists                            23.2%           Hard
21      Merge Two Sorted Lists                          35.2%           Easy
19      Remove Nth Node From End of List                29.2%           Easy

Tips:

while(head){} - after while loop, head is null(last node is processed inside while).

while(head->next){} - after while loop, head is the last node(last node is not processed inside while).

Dummy node \(d\) - make sure not to lose track of head node when looping the list. The code is normally like the following:

For recursive method, be careful to the . Don’t write redundant code for the termination condition! Ensure code is clean and neat!

Naming Convention:

d - dummy node
c - current node, used to loop through the list
h - head of linked list
p - previous node
n - next node
nn - next next node
t - tmp node

Linked List Problems - Stanford CS Education Library

9.2 Partition List

https://leetcode.com/problems/partition-list/

Use p to move from head to end and compare each value with x Create two dummy point, one is used to link points that are <x, another is to link points that are >=x.

Draw a graph to analyze the whole process, or line 13 is very easy to be forgotten!

9.4 143. Reorder List

Given a singly linked list L: L0?L1?…?Ln-1?Ln, reorder it to: L0?Ln?L1?Ln-1?L2?Ln-2?…

You must do this in-place without altering the nodes’ values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

https://leetcode.com/problems/reorder-list/

2017(7-9月) 码农类 硕士 全职 Facebook - 猎头 - 技术电面 |Other在职跳槽
刷题 143 原题印度小哥,说了很多,给我30min coding.前后各交流15min
先说O n^2 解, 又说里On 解,然后开始写
猎头领英上联系的,不知道是不是只能在infra下面选组的
题不难,但不在tag里,如果面同一个组但同学可以看看linked list相关题 求问各位大神白板速度怎么提升,我感觉自己还是废话太多.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=292345

9.5 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …

https://leetcode.com/problems/odd-even-linked-list/

9.6 237. Delete Node in a Linked List

https://leetcode.com/problems/delete-node-in-a-linked-list

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

9.8 138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

https://leetcode.com/problems/copy-list-with-random-pointer

  1. Map from old node to new old, and copy twice!

这题的关键是如何track一个节点是否已经被copy了.假如我们要copy如下list,用指针p1来扫描每个节点,另一个指针p2建立copy.

______
|     |
|     V
1->2->3

p1扫描1时,p2复制1,以及1->next (2), 1->random (3).之后p1, p2分别移到各自的2节点.此时我们必须得知道节点3在之前已经被复制了,并且得知道复制节点的地址.

______
|     |
|     V
1->2->3

所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系.这样每次要建立当前节点p的next和random前,先在hash table中查找.如果找到,则直接连接;否则建立新节点连上,并把和原节点的对应关系存入hash table中.

http://bangbingsyb.blogspot.com/2014/11/leetcode-copy-list-with-random-pointer.html

  • JAVA

这道题本质是一个Graph traversal问题.下面是DFS的写法.

Simliar Problem: Clone Graph

  1. No Extra Sapce

http://blog.csdn.net/linhuanmars/article/details/22463599

http://www.cnblogs.com/TenosDoIt/p/3387000.html

http://fisherlei.blogspot.com/2013/11/leetcode-copy-list-with-random-pointer.html

9.10 Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

https://leetcode.com/problems/merge-k-sorted-lists/

The naive way is to scan heads and find min node per scan. This will take O(N*K) time, where \(N\) is the average length of all lists.

http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html

9.10.2 mergeTwoLists

T: \(O(NlogK)\), S:\(O(K)\)

题目是merge k sorted list 我给了heap的做法 分析了复杂度 接下来是如何用parallel的算法来做 一开始我以为是考多线程 后来小哥说不对 就是一个线程 然后我猜了一个分治法 歪打正着 然后分析复杂度 然后小哥又问 对于分治法 如果有k个processor的话复杂度会变成多少 这个地方我分析的有点卡壳 之前从来没联系过多个处理器情况的复杂度分析 然后小哥给了一下提示 做出来了

http://bit.ly/2xw3D6O

9.12 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

https://leetcode.com/problems/linked-list-cycle-ii

http://www.cnblogs.com/hiddenfox/p/3408931.html

证明其实没那么简单,网上很多错的误导人的证明(比如说\(a==c\)这显然是不对的,设想\(a\)很大,圈很小!!!). 两个指针相遇前可能已经绕了环N,M圈了.设圈的长度为L

The tortoise moves \(d=a+b+NL\), hare moves two times as tortoise \(2d=a+b+ML\), so \(d=(M-N)L=a+b+NL\), and \(a+b=(M-2N)L\).

\(M-2N\)是一个大于0的integer.

So at point Z, if tortoise moves \(a\) step, it will get point Y.

\(a\)不一定等于\(c\),但是可以保证的是,从Z点出发,再走a步肯定到达Y点(虽然完全可能已经绕了好几个圈!!!).

9.13 457. Circular Array Loop

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it’s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be “forward” or "backward’.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element “0”.

Can you do it in O(n) time complexity and O(1) space complexity?

https://leetcode.com/problems/circular-array-loop/

注意The loop must be “forward” or "backward’. 所以这就是为什么[-2, 1, -1, -2, -2]是false的原因

说实话,这道题描述的并不是很清楚,比如题目中有句话说循环必须是forward或是backward的,如果不给例子说明,不太容易能get到point.所谓的循环必须是一个方向的就是说不能跳到一个数,再反方向跳回来,这不算一个loop.比如[1, -1]就不是一个loop,而[1, 1]是一个正确的loop.看到论坛中一半的帖子都是各种需要clarify和不理解test case就感觉很好笑~博主也成功踩坑了.弄清楚了题意后来考虑如何做,由于从一个位置只能跳到一个别的位置,而不是像图那样一个点可以到多个位置,所以这里我们就可以根据坐标建立一对一的映射,一旦某个达到的坐标已经有映射了,说明环存在,当然我们还需要进行一系列条件判断.首先我们需要一个visited数组,来记录访问过的数字,然后我们遍历原数组,如果当前数字已经访问过了,直接跳过,否则就以当前位置坐标为起始点开始查找,进行while循环,将当前位置在visited数组中标记true,然后计算下一个位置,计算方法是当前位置坐标加上对应的数字,由于是循环数组,所以结果可能会超出数组的长度,所以我们要对数组长度取余.当然上面的数字也可能是负数,加完以后可能也是负数,所以光取余还不够,还得再补上一个n,使其变为正数.此时我们判断,如果next和cur相等,说明此时是一个数字的循环,不符合题意,再有就是检查二者的方向,数字是正数表示forward,若是负数表示backward,在一个loop中必须同正或同负,我们只要让二者相乘,如果结果是负数的话,说明方向不同,直接break掉.此时如果next已经有映射了,说明我们找到了合法的loop,返回true,否则建立一个这样的映射,继续循环.

http://www.cnblogs.com/grandyang/p/7658128.html

  • Simplest way to check if two integers have same sign?
(a ^ b) >= 0

https://goo.gl/MqhknK

  • Java

Just think it as finding a loop in Linkedlist, except that loops with only 1 element do not count. Use a slow and fast pointer, slow pointer moves 1 step a time while fast pointer moves 2 steps a time. If there is a loop (fast == slow), we return true, just except there’s only 1 element in the loop. else if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.

http://www.cnblogs.com/EdwardLiu/p/6202015.html

9.14 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.

https://leetcode.com/problems/add-two-numbers/

这道题已经把数字颠倒过来了,所以就比较简单,直接从头到尾循环了事.

注意考虑5+5这种情况.

如果数字没有颠倒,应该要用recursive搞定. 果然真有一题下面.

9.15 445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

仔细想了下直接递归好像还不太容易. 上面的例子递归到最后肯定是3 + NULL,其他例子可能是3->4->5->NULL + NULL,那么返回什么给上一层使用呢? 上一层如果是2->3->4->5->NULL + 1->NULL,1其实应该和5相加,这样就破坏了返回的结果.所以这样递归好像不行.

要不先算出两个list的长度,然后把两个list尾部对齐再递归?这样应该可行!

http://www.cnblogs.com/grandyang/p/6216480.html

借助stack的方法很简单.

9.16 306. Additive Number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example: “112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Follow up: How would you handle overflow for very large input integers?

https://leetcode.com/problems/additive-number/

思路: 一个基本的思想就是确定了第一个和第二个数之后, 以后的数就是验证了, 所以只要枚举第一和第二个数, 然后不断验证下面的字符串子串是否是前两个数的和即可. 因为数字可能超出整数的范围, 因此在验证一个数是否是另外两个和的时候, 可以用字符串相加来模拟整数相加. 另外需要注意的是’0’字符, 如果他在子串的首位, 那么他只能以“0”的形式存在.

9.23 382. Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

https://leetcode.com/problems/linked-list-random-node/

Reservoir Sampling