LeetCode链表简单题

一、21合并两个有序链表

代码如下：

class solution:
    def mergetwolists(self, l1: listnode, l2: listnode) -> listnode:
        # 首先对特殊情况进行处理，l1 l2 为空的时候
        if not (l1 and l2) : # 这个表达式的意思只要l1 l2 不全为真就符合条件
            return l1 or l2 
        elif l1.val > l2.val:  # 判断哪一个值比较小，然后保留哪一项 
            l2.next = self.mergetwolists(l2.next,l1)  # 递归思想的精髓
            return l2  # 返回小的这一项
        else :
            l1.next = self.mergetwolists(l1.next,l2) 
            return l1
# 注意：l1 l2 表示的不是整个链表，而只是每一个结点

# 这个是别人给的题解，大佬写的很好。
class solution:
    def mergetwolists(self, l1: listnode, l2: listnode) -> listnode:
        if l1 and l2: # 判断l1 是否为空
            if l1.val > l2.val : l1,l2 = l2,l1 # 始终让l1 为小值
            l1.next = self.mergetwolists(l1.next,l2) # 递归的精髓 
        return l1 or l2

二、83删除链表重复的元素

class solution:
    def deleteduplicates(self, head: listnode) -> listnode:
        if not head :return head # 首先判断链表是否为空，若为空直接返回
        head1 = head
        l = [] # 定义一个空的列表 用来存放已经遍历过的链表结点
        l.append(head.val) # 将遍历过的链表结点添加进入列表中
        while head and head.next: # 当前结点和下一个结点都为真继续
            if head.next.val in l : # 若下一节点的值已经在列表中
                head.next = head.next.next # 进行删除操作，跳过下一节点，直接指向下下结点
            else:
                l.append(head.next.val) # 将结点添加进入列表
                head = head.next # 进行遍历
        return head1 # 返回删除重复元素后的链表

三、141环形链表

# 解题思路；利用快慢指针，一个指针快，另一个慢，若链表有环，则总有相遇的时候
class solution(object):
    def hascycle(self, head):
        """
        :type head: listnode
        :rtype: bool
        """
        if not head or not head.next : # 若链表中没有元素，或者只有一个元素，则不可能成环
            return false
        fast = head
        slow = head
        while fast:
            if fast.next == none: # 若快指针可以走到头，则肯定没有环
                return false
            else :
                fast = fast.next.next # 快指针每次走两步
                slow = slow.next # 慢指针走一步
            if slow == fast: # 当快慢指针相遇
                return true
        return false # 当快指针为none时退出

四、160相交链表

class solution(object):
    def getintersectionnode(self, heada, headb):
        """
        :type head1, head1: listnode
        :rtype: listnode
        """
        if not heada or not headb: # 若两个链表中其中一个链表为空则不可能相交
            return none
        length1 = 0 # 用来接收heada链表的长度
        length2 = 0
        h1 = heada
        h2 = headb
        while h1: # 遍历链表算出两个链表的长度
            length1 += 1
            h1 = h1.next
        while h2:
            length2 += 1
            h2 = h2.next
        if length1 > length2: # 让比较长的链表先走
            for i in range(length1 - length2):
                heada = heada.next
        elif length1 < length2:
            for i in range(length2 - length1):
                headb = headb.next
        while heada: # 现在两个指针处于同一位置
            if heada == headb: # 判断是否为同一节点
                return heada
            heada = heada.next
            headb = headb.next
        return none

五、203移除链表元素

class solution(object):
    def removeelements(self, head, val):
        """
        :type head: listnode
        :type val: int
        :rtype: listnode
        """
        if not head:return head # 判断是否为空链表
        head1 = head # 用head1返回新的链表
        while head: # 找到第一个不需要删除的链表
            if head.val == val: # 需要删除时，将head1等于head的下一节点
                head1 = head.next
                head = head.next
            else:
                break
        while head and head.next: # 进行链表的遍历，进行删除所给的元素
            if head.next.val == val:
                head.next = head.next.next
            else :
                head = head.next
        return head1 # 返回新的链表

六、234回文链表

# 用快慢指针的方法找到链表的中间节点，然后将后半段链表进行反转，在判断
class solution:
    def ispalindrome(self, head: listnode) -> bool:
        if not head or not head.next : # 若链表为空或为一个元素，则链表为回文链表
            return true
        fast = head
        slow = head # 快慢指针 快指针走两步，慢指针走一步
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow  # 此时slow为中点指针
        pre = none
        # 将后半段链表表反转
        while slow:
            slow.next,pre,slow = pre,slow,slow.next 
            # 不可以分开写成三个语句，python特有，在c语言中这样写是错误的
            # 他们这三个语句的执行是相同，没有先后之分。
        # 此时后半段列表的头指针为pre
        while head != mid:
            if head.val != pre.val:
                return false
            pre = pre.next
            head = head.next
        return true