• 字节题库

NC78 反转链表

NC78 反转链表

• 迭代法

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        p=pHead
        pre=None
        while p:
            aft=p.next
            p.next=pre
            pre=p
            p=aft
        return pre

• 递归法

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        last=self.ReverseList(pHead.next)
        pHead.next.next=pHead
        pHead.next=None
        return last

NC140 排序

NC140 排序

• 快速排序

def quick_sort(nums, left, right):
    l,r=left,right
    if l>=r:
        return 
    pivot=nums[l]
    while l<r:
        while l<r and nums[r]>pivot: # pivot写错
            r-=1
        if l<r:
            nums[l]=nums[r]
            l+=1
        while l<r and nums[l]<pivot:
            l+=1
        if l<r:
            nums[r]=nums[l]
            r-=1
    nums[l]=pivot
#     print(nums, l)
    quick_sort(nums, left, l-1)
    quick_sort(nums, l+1, right)
        

class Solution:
    def MySort(self , arr ):
        n=len(arr)
        quick_sort(arr,0,n-1)
        return arr

↑Python代码居然超时。。我去隔壁LC是可以的。。CPP实现↓

class Solution {
public:
    void quick_sort(vector<int>& arr,int left,int right){
        int l=left, r=right;
        if(l>=r) return;
        int pivot=arr[l];
        while(l<r){
            while(l<r && arr[r]>pivot) r--;
            if(l<r){
                arr[l]=arr[r];
                l++;
            }
            while(l<r && arr[l]<pivot) l++;
            if(l<r){
                arr[r]=arr[l];
                r--;
            }
            arr[l]=pivot;
        }
        quick_sort(arr,left,l-1);
        quick_sort(arr,l+1,right);
    }
    
    vector<int> MySort(vector<int>& arr) {
        int n=arr.size();
        quick_sort(arr, 0, n-1);
        return arr;
    }
};