Line data    Source code

       1              : // Copyright (c) 2022 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              : // Created: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include "list.h"
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25              :     using ListNode = leetcode::list::ListNode;
      26            2 :     leetcode::list::ListNode* reverseList(leetcode::list::ListNode* head) {
      27            2 :         if (!head) {
      28            0 :             return nullptr;
      29              :         }
      30            2 :         leetcode::list::ListNode* pre = nullptr;
      31            2 :         leetcode::list::ListNode* cur = head;
      32           11 :         while (cur) {
      33            9 :             leetcode::list::ListNode* next = cur->next;
      34            9 :             cur->next = pre;
      35            9 :             pre = cur;
      36            9 :             cur = next;
      37              :         }
      38            2 :         return pre;
      39              :     }
      40              : 
      41              :     // 递归实现
      42            1 :     ListNode* reverseList2(ListNode* head) {
      43            1 :         if (!head || !head->next) {
      44            0 :             return head;
      45              :         }
      46            1 :         ListNode* newhead = reverseList(head->next);
      47            1 :         head->next->next = head;
      48            1 :         head->next = nullptr;
      49            1 :         return newhead;
      50              :     }
      51              : };
      52              : } // namespace
      53              : 
      54            4 : TEST(Leetcode, reverse_linked_list) {
      55            1 :     Solution s;
      56              :     {
      57            1 :         leetcode::list::ListNode* head = leetcode::list::create({1, 2, 3, 4, 5});
      58            1 :         leetcode::list::ListNode* ret = s.reverseList(head);
      59            1 :         std::vector<int> exp = {5, 4, 3, 2, 1};
      60            1 :         int i = 0;
      61            1 :         leetcode::list::ListNode* cur = ret;
      62            6 :         while (cur) {
      63            5 :             EXPECT_EQ(exp[i++], cur->val);
      64            5 :             cur = cur->next;
      65              :         }
      66            1 :         destroy(ret);
      67            1 :     }
      68              : 
      69              :     {
      70            1 :         leetcode::list::ListNode* head = leetcode::list::create({1, 2, 3, 4, 5});
      71            1 :         leetcode::list::ListNode* ret = s.reverseList2(head);
      72            1 :         std::vector<int> exp = {5, 4, 3, 2, 1};
      73            1 :         int i = 0;
      74            1 :         leetcode::list::ListNode* cur = ret;
      75            6 :         while (cur) {
      76            5 :             EXPECT_EQ(exp[i++], cur->val);
      77            5 :             cur = cur->next;
      78              :         }
      79            1 :         destroy(ret);
      80            1 :     }
      81            1 : }