链表高频算法题及其解法

整理之后想起来LeetCode自己家出过一个类似的汇总Orz,大概是最近真的太闲了,想整理下刷过的题目,老实讲之前刷的题并不多。 LeetCode领扣的公众号做得很好,有时间回去翻翻看。

单链表反转

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
if pHead == None:
return pHead
pre = next = None
while pHead != None:
next = pHead.next
pHead.next = pre
pre = pHead
pHead = next
return pre

链表中环的检测

题目描述

141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
# Given an empty list
if not head:
return False

# Initialize two pointers
slow = head
fast = head.next
while fast and slow:
# Two pointers would finally come to the same node
# when there is a cycle
if fast == slow:
return True
if fast.next:
fast = fast.next.next
slow = slow.next
# fast.next is None means that there is no cycle
else:
break

return False

有序链表合并

题目描述

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.

Example:

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

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
returnNode = ListNode(-1)
headNode = returnNode

while l1 != None and l2 != None:
if l1.val <= l2.val:
returnNode.next = l1
l1 = l1.next
else:
returnNode.next = l2
l2 = l2.next
returnNode = returnNode.next

if l1 == None:
returnNode.next = l2
elif l2 == None:
returnNode.next = l1

return headNode.next

删除链表中倒数第n个节点

题目描述

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

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head

l = r = dummy

for _ in range(n+1):
r = r.next

while r != None:
r = r.next
l = l.next


l.next = l.next.next

return dummy.next

求链表的中间节点

题目描述

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

题解

1
2
3
4
5
6
7
class Solution(object):
def middleNode(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow