head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2:
输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
提示:
1
和 100
之间。解题思路:
采用快慢指针,慢指针走一步,快指针走两步,当快指针到达尾结点时,慢指针就是中间节点;
图一:链表节点数为奇数时,当fast->next == nullptr时,slow就是中间节点;
图二:链表节点数为偶数时,当fast->next->next == nullptr时,slow->next就是第二个中间节点;
1 #include <iostream> 2 #include <vector> 3 4 using namespace std; 5 6 class ListNode { 7 public: 8 ListNode() : val(0), next(nullptr) {} 9 ListNode(int x) : val(x), next(nullptr) {} 10 ListNode(int x, ListNode *next) : val(x), next(next) {} 11 12 public: 13 int val; 14 ListNode *next; 15 }; 16 17 class Solution { 18 public: 19 ListNode* middleNode(ListNode* head) { 20 ListNode *slow = head; 21 ListNode *fast = head; 22 if (head == nullptr) { 23 return nullptr; 24 } 25 while (fast->next != nullptr && fast->next->next != nullptr) { 26 slow = slow->next; 27 fast = fast->next->next; 28 } 29 return (fast->next == nullptr) ? slow : slow->next; 30 } 31 void insertNodeAtTail(ListNode *&head, int val) { 32 ListNode *newNode = new ListNode(val); 33 ListNode *currentNode = head; 34 if (head == nullptr) { 35 head = newNode; 36 return; 37 } 38 while (currentNode->next != nullptr) { 39 currentNode = currentNode->next; 40 } 41 currentNode->next = newNode; 42 return; 43 } 44 void printfListNode(ListNode *head) { 45 while (head != nullptr) { 46 std::cout << head->val << "->"; 47 head = head->next; 48 } 49 std::cout << "NULL" << endl; 50 return; 51 } 52 }; 53 int main() 54 { 55 Solution *test = new Solution(); 56 vector<int> vec = {1, 2, 3, 4, 5, 6, 7 }; 57 ListNode *head = nullptr; 58 for (const auto &v : vec) { 59 test->insertNodeAtTail(head, v); 60 } 61 test->printfListNode(head); // 1->2->3->4->5->6->7->NULL 62 63 ListNode *midNode = test->middleNode(head); 64 if (midNode != nullptr) { 65 std::cout << "midNode's value:" << midNode->val << endl; // 4 66 } else { 67 std::cout << "midNode's value is nullptr!" << endl; 68 } 69 test->insertNodeAtTail(head, 8); // 1->2->3->4->5->6->7->8->NULL 70 test->printfListNode(head); 71 midNode = test->middleNode(head); 72 if (midNode != nullptr) { 73 std::cout << "midNode's value:" << midNode->val << endl; // 5 74 } else { 75 std::cout << "midNode's value is nullptr!" << endl; 76 } 77 delete test; 78 system("pause"); 79 return 0; 80 }
运行结果: