算法-数据结构-链表

1.链表反转

class Node():
    def __init__(slef,data):
        self.next=None
        self.data=data

# 方法一
def reverse(head):
    if head.next is None:
        return head

    next=head.next
    head.next=None
    current_next=revers(next)
    next.next=head
    return current_next

# 方法二
def swap_reverse(head):
    cur,prev=head,None
    while cur:
        cur.next,prev,cur=prev,cur,cur.next
    return prev

两两交换链表中的节点

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

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
       if head is None or head.next is None : return head
       next = head.next
       head.next=self.swapPairs(next.next)
       next.next=head
       return next 

3.判断链表是否有环

# 正常思维
item = set()
class Solution(object):

    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        global item
        if head is None or head.next is None:
            return False
        a = item & {head}
        if len(a) != 0:
            return True
        else:
            item.update({head})
            return self.hasCycle(head.next)
# 龟兔赛跑
class Solution(object):

    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast,slow=head,head
        while fast and fast.next and fast.next.next:
            slow,fast=slow.next,fast.next.next
            if slow==fast:
                return True     
        return False

2.链表合并

class Node():
    def __init__(slef,data):
        self.next=None
        self.data=data

def merge(head1,head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.data<=head2.data:
        head1.next=merge(head1.next,head2)
        return head1
    else:
        head2.next=merger(head1,head2.next)
        return head2