0%

• 依照leetcode定义 自己写的链表创建/打印方法，便于测试
• 19 . Remove Nth Node From End of List
• 21. Merge Two Sorted Lists
• 23. Merge k Sorted Lists
• 24. Swap Nodes in Pairs
• 25. Reverse Nodes in k-Group
• 61. Rotate List
• 86. Partition List
• 138 . Copy List with Random Pointer
• 141 . Linked List Cycle
• 142. Linked List Cycle II
• 143 . Reorder List
• 147. Insertion Sort List
• 148. Sort List
• 160. Intersection of Two Linked Lists
• 203 . Remove Linked List Elements
• 206 . Reverse Linked List
• 234 . Palindrome Linked List
• 237 . Delete Node in a Linked List

update:2015-7-14

• add a 203 solution code:

• using recursion and reference to delete linklist node which value equals x
• 单项链表递归删除，使用引用

update:2015-06-23

• update some codes ,more simple and cool than before.
• solve problems 203 and 206

C

C++

Python

## 二、题解

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.

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

C++

Java

Python

### 19.  leetcode Remove Nth Node From End of List

Given a linked list, remove the _n_th node from the end of list and return its head.

For example,

Note: Given n will always be valid. Try to do this in one pass.

Python

### 21. leetcode Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

C++:

Python

### 23. Merge k Sorted Lists

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

C++

Python

### 24. Swap Nodes in Pairs

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

C++

Python

### 25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

C++

### 61. Rotate List

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

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

C++

Python

### 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

C++

Python

discuss看到的另一种写法：

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

Python

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

C

C++

Java

Python

### 142.  Linked List Cycle II

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

Follow up: Can you solve it without using extra space?

1.  同样的判圈法（见下面详细说明）
2.  hash表：遍历的同时存进hash表，若遇到重复的返回即可。

fast指针的速度为慢指针slow的两倍，如果有环，那么fast指针一定会追上慢指针slow！

• slow 指针距离= a + b
• fast指针距离 = a + b + c + b

• 2(a + b) = (a + b + c + b)
• 化简得 a = c

C++

Java

Python

C++

Python

### 143. Reorder List

Given a singly linked list L: _L_0→_L_1→…→_L__n_-1→_L_n, reorder it to: _L_0→_L__n_→_L_1→_L__n_-1→_L_2→_L__n_-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}.

1. 求中点（可以先遍历找到中点，但更好的是快慢指针）
2. 翻转后面的链表
3. 两个链表合并

C++

Python

### 147. leetcode Insertion Sort List

Sort a linked list using insertion sort.

C/C++

Python

### 148. leetcode Sort List

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

### 160. leetcode Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

• 用哈希表O(n+m) 空间为O(m)或者O(n)
• 由于两个链表可能一长一短，故对其同时进行遍历时一定有一个先到达结尾。如果链表A先到结尾，则指向B的开头，如果B先到达结尾，则指向A的开头。然后继续进行遍历，这样两个链表一定同时到达结尾。当到达结尾时，如果之前最早出现过两个指针指向地址相同的，那么就是所求解。这样正确的原因在于，如果两个链表尾部有重复的，那么两个链表链接起来不管是a+b还是b+a尾部也一定是一样的。- - 然后长度还一样，没啥好说的了。

c 的hash表(介绍详见leetcode哈希表)

Python

C++

Java

Python

### 203. leetcode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

• 建一个哨兵节点统一删除操作，这个没啥好说的，代码在比较下面
• 使用C++引用+递归

C++ 引用+递归

• 当L->val == x时候，当前的结点为待删除的结点，故用指针指向当前结点（p = L)，并且让当前结点指向下一个结点(L=L->next)，之后我们删除该结点(delete p)，并且调用del_x(L,x); （毕竟现在的L可能也等于x）
• 当L->val != x时候，当前结点并不是要删除的结点，调用del_x(L->next,x);

1. 初始L指向A，非待删除结点，执行 del_x(L->next,x); 此时L->next 指向了B
2. L指向B， 需要删除， L = L->next 的时候，因为此时的L使用引用，其值为A->next，效果等同于A->next = B ->next 就是说A->next指向了C， 删除B后，执行del_x(L,x);
3. L指向C，非待删除，调用del_x(L->next,x);
4. L为NULL，return

C

C++

Python

### 206.  leetcode Reverse Linked List

C

C++(和C差不多，不必看)

python (其实都差不多好不好 (╯‵□′)╯︵┻━┻)

cur和pre双指针，每次pre为cur后面一个元素，遍历的时候将pre->next指向cur即可

C++

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

### 237 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.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

C++

Python

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.

C++

Python