C/C++教程

[AcWing 35] 反转链表

本文主要是介绍[AcWing 35] 反转链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

image

点击查看代码 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next)   return head;
        auto a = head, b = a->next;
        while (b) {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        head->next = NULL;
        return a;
    }
};
  1. 当是空链表或只有一个结点时，直接返回头结点 head；
  2. 当 b 不为空时，a 指向当前结点 p，b 指向 p->next，c 指向 p->next->next，每次将 b->next = a，并移动指针 a = b， b = c；
  3. head 此时指向的是新链表的尾结点，head->next = NULL；
  4. 新链表的头结点是 a；
点击查看代码 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next)   return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};
这篇关于[AcWing 35] 反转链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航