链表相关算法（python）

目录

链表结构定义

x
class ListNode(object):
​
    def __init__(self, val, next):
        self.val = val
        self.next = next

链表反转

题目：https://leetcode-cn.com/problems/reverse-linked-list/

1. 解法一

   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
   

2. 解法二

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

带环链表问题

1. 如何检测是否带环

   快指针走2步，慢指针走1步，如果有环，则肯定会相遇。

2. 求环的节点数

   从相遇点开始走，并计数，再次到达相遇点则计数结束。

3. 求环入口

   在已知环的结点数后，其中一个指针先走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/

解题思路：

1. 因为k可能大于链表长度，所以先求链表长度size， 在用k对size取余。
2. 把后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