leetcode 链表

本次题解包括:

  • 依照leetcode定义 自己写的链表创建/打印方法,便于测试
  • 2. Add Two Numbers
  • 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
  • 817. Linked List Components

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

 

二、题解

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.

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

题目地址:leetcode Add Two Numbers

题目大意: 给定两个非空链表,链表已经是逆序,求他们的和。

思路:

利用哨兵节点代码更好写,直接加即可。

C++

Java

Python

 

 


 

 

19.  leetcode Remove Nth Node From End of List

Given a linked list, remove the nth 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.

题目地址:leetcode Remove Nth Node From End of List

思路:

如果可以求出链表的长度,那么很简单:

但是如果要求只遍历一次呢,我们就不能求长度了,可以用两个指针,一个指针faster先遍历n个节点,然后在一起遍历到faster->next为空的时候。

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.

题目地址:leetcode Merge Two Sorted 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.

题目地址:leetcode Merge k Sorted Lists

题目大意:给定k个排好序的链表,合并成一个有序的

思路:

用堆来合并。复杂度O(Nlogk) N为最终合并完的链表的长度。

C++

当然也可以新建一个类来做比较

 

Python

 

 


 

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

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.

题目地址:leetcode Swap Nodes in Pairs

题目大意:交换链表中相邻两个元素

思路:直接交换即可。。。

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

题目地址:leetcode Reverse Nodes in k-Group

题目大意: 给定数字k,要求将这链表分为k组,每组进行逆置

比上面一题难处理一点。

主要是写个逆置的function,每次数到k个数调用。

需要注意的是本题是将链表的块进行调换,而不是交换元素值,需要特别注意调换后和调换前的块的位置关系。

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.

题目地址:leetcode Rotate List

题目大意: 给定一个链表,和k,要求从结尾开始算起第k个位置旋转到开头

思路:进行两次扫描,第一次扫描算出链表长度并且标记尾部。第二次扫描只需要找到右边算起第 k % len +1的位置即可。

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.

题目地址:leetcode Partition List

题目大意:给定一个链表和一个数字x,要求对链表元素进行划分。将小于x的元素放在大于等于x元素的左边。

思路:

两个指针一个指向小于的,一个指向大于等于的,然后遍历链表即可。

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.

题目地址:leetcode Copy List with Random Pointer

题目大意:给定一个链表,链表中有个指针random,它随机指向该链表中的任何结点,现在请你复制这个链表(深度复制)

思路:需要深度复制的话,难点在于如何更改random指针,而不是照搬。(照搬的话原链表要是修改那么你random输出的也会被改)我直接用字典(dict c++也叫map)了。

 

 

 

 

 


 

 

141. Linked List Cycle

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

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

题目地址:leetcode Linked List Cycle

题意:给一个链表,判断其是否有环。

思路:假设两个小孩一直在绕操场跑,其中小孩A速度是小孩B的两倍,那么A一定会一次次的“追上”小孩B。所以两个指针,一个每次前进一步,一个两步,直到为空(无环)或者相等为止(有环)

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?

题目地址:leetcode Linked List Cycle II

题意:给一个链表,返回其开始环的地方,如果没有,返回NULL

思路:

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

方法一:

上面的判断有圈子的方法我们在回顾一下:

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

如上图所示:假设非环的部分长为a,第一次相遇点z离环的起点的y距离为b,slow指针在环上移动的距离不会超过一圈,为什么?考虑极端的情况,就是没有上图a那一段,那么快慢指针同时从y点出发,第一次相遇则恰好在y点处。而如果有a那一段的话,就不会走到y点了。

那么有:

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

由于fast是slow的两倍,因此有

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

因此,当有环的时候,fast和slow相遇为z那么将fast或者slow重新指向开头head,然后各走a步,就会相遇于点y

换句话说:在z处走c也会回到y,从head走c也到达y。

C++

Java

python

 

 

 

方法二hash:(C的话得手写hash=v=懒)

C++

Python

 

 


 

143. Reorder List

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}.

题目地址:leetcode Reorder List

题目大意:给定一个链表 L0→L1→…→Ln-1→Ln,,返回L0→Ln→L1→Ln-1→L2→Ln-2的顺序

思路:分为3步:

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

C++

 

Python

 

 

 

 

 

147. leetcode Insertion Sort List

Sort a linked list using insertion sort.

题目地址:leetcode Insertion Sort List

题意:对一个链表进行插入排序

思路:用tail标记包括tail之前已排好序的链表。对于cur=tail.next,先和tail比较,若大于等于,则不用排序,否则从头开始查找插入位置。

还有就是我用了哨兵结点,便于插入。

C/C++

 

Python

 

 

 

 

 

148. leetcode Sort List

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

题目地址:leetcode Sort List

题意:给定一个链表,要求用O(n log n) 的复杂度进行排序。

思路:合并排序或者快排都行

 

 

 

 

 

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.

题目地址:leetcode Intersection of Two Linked Lists

题意:给定两个链表,返回其重复的第一个位置。

思路:

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

方法一(hash)

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

题目地址:leetcode Remove Linked List Elements

题意:给定一个链表,删除值为val的全部元素

思路:

  • 建一个哨兵节点统一删除操作,这个没啥好说的,代码在比较下面
  • 使用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,2,3 删除数为2 为例子。(下面把1 , 2, 3 内存地址称为A,B,C,方便说明)

  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

Reverse a singly linked list.

题目地址:leetcode Reverse Linked List

题意:链表逆序

思路:每次遍历到某个元素把它变为“头”即可

C

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

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

 

 

234. Palindrome Linked List

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?

题目地址:leetcode Palindrome Linked List

题意:给定一个链表,判断它是否为回文串

思路:最简单的方法是直接保存下来对比一下时间空间复杂度均为O(n)

 

第二种方法是将链表分为两半,前一半或者后一半逆序然后比较。

 

 

 

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.

题目地址:leetcode Delete Node in a Linked List

题意:给定指向要删除的节点的指针,删除这个节点。

思路:把这个指针内容复制为下一个,然后删除下一个即可。

C++

Python

 

 


 

817. Linked List Components

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.

题目地址:leetcode Linked List Components

题目大意:给定一个链表和一个数组G,让你判断G中包含链表中几个“连接的部分”。连接的部分定义为:两个值连续出现即为一个连接部分。

思路:把G变为set,遍历数组,记录前一个是否为连接的从而进行分组。

C++

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 链表
本文地址:https://www.hrwhisper.me/leetcode-linklist/

听说长得好看的已经打赏了

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *