java 解法, 执行用时: 6 ms, 内存消耗: 67.3 MB, 提交时间: 2024-01-03 09:25:26

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        head = reverseList(head);
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val > cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return reverseList(head);
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

cpp 解法, 执行用时: 384 ms, 内存消耗: 153 MB, 提交时间: 2024-01-03 09:24:48

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    ListNode *reverseList(ListNode *head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
public:
    ListNode *removeNodes(ListNode *head) {
        head = reverseList(head);
        ListNode *cur = head;
        while (cur->next) {
            if (cur->val > cur->next->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return reverseList(head);
    }
};

cpp 解法, 执行用时: 328 ms, 内存消耗: 157.5 MB, 提交时间: 2024-01-03 09:24:28

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        if ( head->next == nullptr ) return head;  // 输入保证链表不为空
        ListNode *node = removeNodes(head->next);  // 返回的链表头一定是最大的
        if ( node->val > head->val ) return node;  // 删除 head
        head->next = node;  // 不删除 head
        return head;
    }
};

java 解法, 执行用时: 20 ms, 内存消耗: 73.4 MB, 提交时间: 2024-01-03 09:21:34

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        if ( head.next == null ) return head;  // 输入保证链表不为空
        ListNode node = this.removeNodes(head.next);  // 返回的链表头一定是最大的
        if ( node.val > head.val ) return node;  // 删除 head
        head.next = node;  // 不删除 head
        return head;
    }
}

python3 解法, 执行用时: 912 ms, 内存消耗: 56.1 MB, 提交时间: 2022-12-01 09:56:11

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head = self.reverseList(head)
        while cur.next:
            if cur.val > cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return self.reverseList(head)

golang 解法, 执行用时: 188 ms, 内存消耗: 9.7 MB, 提交时间: 2022-12-01 09:55:49

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
	var pre, cur *ListNode = nil, head
	for cur != nil {
		nxt := cur.Next
		cur.Next = pre
		pre = cur
		cur = nxt
	}
	return pre
}

func removeNodes(head *ListNode) *ListNode {
	head = reverseList(head)
	cur := head
	for cur.Next != nil {
		if cur.Val > cur.Next.Val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return reverseList(head)
}

golang 解法, 执行用时: 248 ms, 内存消耗: 15.8 MB, 提交时间: 2022-12-01 09:54:27

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
	if head.Next == nil { // 输入保证链表不为空
		return head
	}
	node := removeNodes(head.Next)
	if node.Val > head.Val { // 返回的链表头一定是最大的
		return node // 删除 head
	}
	head.Next = node // 不删除 head
	return head
}

python3 解法, 执行用时: 1144 ms, 内存消耗: 153 MB, 提交时间: 2022-12-01 09:54:05

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None: return head  # 输入保证链表不为空
        node = self.removeNodes(head.next)  # 返回的链表头一定是最大的
        if node.val > head.val: return node  # 删除 head
        head.next = node  # 不删除 head
        return head