链表相关算法(python)
目录
链表结构定义
x
class ListNode(object):
def __init__(self, val, next):
self.val = val
self.next = next
链表反转
题目:https://leetcode-cn.com/problems/reverse-linked-list/
解法一
x
class Solution:
def reverseList(self, head):
"""
链表反转 O(n)时间,O(1)空间
步骤:
1 -> 2 -> 3 -> 4
2 -> 1 -> 3 -> 4
3 -> 2 -> 1 -> 4
4 -> 3 -> 2 -> 1
done
"""
p = head
while(p and p.next):
node = p.next
p.next = node.next
node.next = head
head = node
return head
解法二
xxxxxxxxxx
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur, pre = head, None
while cur:
cur.next, pre, cur = pre, cur, cur.next
return pre
有序链表合并
https://leetcode-cn.com/problems/merge-two-sorted-lists/
同时遍历两个链表,比较大小,把小的结点取下来到新的串。
xxxxxxxxxx
步骤: head1->1->3->9 head2->2->3->10
head->1
head->1->2
head->1->2->3
head->1->2->3->3
head->1->2->3->3->9
head->1->2->3->3->9->10
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 or not l2:
return l1 or l2
if l1.val > l2.val:
head = l2
l2 = l2.next
else:
head = l1
l1 = l1.next
tail = head
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
tail = tail.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return head
带环链表问题
如何检测是否带环
快指针走2步,慢指针走1步,如果有环,则肯定会相遇。
求环的节点数
从相遇点开始走,并计数,再次到达相遇点则计数结束。
求环入口
在已知环的结点数后,其中一个指针先走n步,然后一起走,相遇点即为入口点。
删除链表的倒数第N个节点
解决方法: 快慢指针
xxxxxxxxxx
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
slow, fast = head, head
for i in range(n):
fast = fast.next
if not fast:
return head.next
while fast and fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
求链表的中间节点
https://leetcode-cn.com/problems/middle-of-the-linked-list/
解题思路: 快慢指针
xxxxxxxxxx
class Solution:
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow, fast = head, head
while fast and fast.next:
if fast.next:
fast = fast.next.next
else:
fast = fast.next
slow = slow.next
return slow
旋转链表
https://leetcode-cn.com/problems/rotate-list/
解题思路:
- 因为k可能大于链表长度,所以先求链表长度size, 在用k对size取余。
- 把后
k % size
个节点,接到链首。
xxxxxxxxxx
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or not head.next:
return head
size = 1
tail = head
while tail.next:
size += 1
tail = tail.next
tail.next = head
p = head
for i in range(size - k % size -1):
p = p.next
head, p.next = p.next, None
return head