Line data    Source code

       1              : // Copyright (c) 2024 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : 
      17              : #include <gtest/gtest.h>
      18              : 
      19              : #include "list.h"
      20              : 
      21              : namespace {
      22              : class Solution {
      23              : public:
      24              :     using ListNode = leetcode::list::ListNode;
      25            2 :     leetcode::list::ListNode* reverseList(leetcode::list::ListNode* head) {
      26            2 :         if (!head) {
      27            0 :             return nullptr;
      28              :         }
      29            2 :         leetcode::list::ListNode* pre = nullptr;
      30            2 :         leetcode::list::ListNode* cur = head;
      31           11 :         while (cur) {
      32            9 :             leetcode::list::ListNode* next = cur->next;
      33            9 :             cur->next = pre;
      34            9 :             pre = cur;
      35            9 :             cur = next;
      36              :         }
      37            2 :         return pre;
      38              :     }
      39              : 
      40              :     // 递归实现
      41            1 :     ListNode* reverseList2(ListNode* head) {
      42            1 :         if (!head || !head->next) {
      43            0 :             return head;
      44              :         }
      45            1 :         ListNode* newhead = reverseList(head->next);
      46            1 :         head->next->next = head;
      47            1 :         head->next = nullptr;
      48            1 :         return newhead;
      49              :     }
      50              : };
      51              : } // namespace
      52              : 
      53            4 : TEST(Leetcode, reverse_linked_list) {
      54            1 :     Solution s;
      55              :     {
      56            1 :         leetcode::list::ListNode* head = leetcode::list::create({1, 2, 3, 4, 5});
      57            1 :         leetcode::list::ListNode* ret = s.reverseList(head);
      58            1 :         std::vector<int> exp = {5, 4, 3, 2, 1};
      59            1 :         int i = 0;
      60            1 :         leetcode::list::ListNode* cur = ret;
      61            6 :         while (cur) {
      62            5 :             EXPECT_EQ(exp[i++], cur->val);
      63            5 :             cur = cur->next;
      64              :         }
      65            1 :         destroy(ret);
      66            1 :     }
      67              : 
      68              :     {
      69            1 :         leetcode::list::ListNode* head = leetcode::list::create({1, 2, 3, 4, 5});
      70            1 :         leetcode::list::ListNode* ret = s.reverseList2(head);
      71            1 :         std::vector<int> exp = {5, 4, 3, 2, 1};
      72            1 :         int i = 0;
      73            1 :         leetcode::list::ListNode* cur = ret;
      74            6 :         while (cur) {
      75            5 :             EXPECT_EQ(exp[i++], cur->val);
      76            5 :             cur = cur->next;
      77              :         }
      78            1 :         destroy(ret);
      79            1 :     }
      80            1 : }