题目大意:反转一个单向链表
Problem:
https://leetcode.com/problems/reverse-linked-list/description/
Reverse a singly linked list.
Solution 1:
Tracking prev / curr / next node
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 9 ms class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; ListNode* next; while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 0 ms class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; ListNode next; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } } |
Python 3
1 2 3 4 5 6 7 8 9 10 11 |
""" Author: Huahua Running time: 48 ms """ class Solution: def reverseList(self, head): prev, curr, nxt = None, head, None; while curr: nxt, curr.next = curr.next, prev prev, curr = curr, nxt return prev |