(LeetCode)链表
程序员文章站
2022-05-06 20:30:14
...
0. 总结
链表问题可以用递归或者循环解决,相对来讲,循环解决更加直观,可以优先使用。
1. 反转链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
笨办法
1. 遍历链表,生成一个数组;
2. 根据数组,倒序创建链表;
聪明办法
改指针方向
"""
cur = head
pre = None
while cur is not None:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
2. 合并两个有序链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
笨办法:
遍历两个链表,得到数组;将数组排好序;生成一个新的链表;
聪明解法:
递归
"""
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
if l1.val >= l2.val:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
上一篇: 使用JDBC对数据库进行增删改查操作
下一篇: 某蝶公司笔试题