剑指offer15

剑指offer15:反转链表

题目描述

题目描述
输入一个链表,反转链表后,输出新链表的表头。

解法一:基于头插法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* h = NULL;
        for (ListNode* p = pHead; p; ) {
            ListNode* tmp = p->next;
            p->next = h;
            h = p;
            p = tmp;
        }
        return h;
    }
};

解法二:基于堆栈的方法

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL || pHead->next == NULL)
        {
            return pHead;
        }
        ListNode * p = pHead;
        ListNode * newHead;
        stack<ListNode *> stack1;
        while (p->next != NULL)
        {
            stack1.push(p);
            p = p->next;
        }
        newHead = p;
        while (!stack1.empty())
        {
            p->next = stack1.top();
            p = p->next;
            stack1.pop();
        }
        p->next = NULL;
        return newHead;

    }
};

   转载规则


《剑指offer15》 赵小亮 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
剑指offer16 剑指offer16
剑指offer16:合并两个排序的链表 题目描述题目描述 输入两个单调递增的链表,输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则。 解法一:基于递归的方法class Solution { public: Li
2020-05-13
下一篇 
剑指offer14 剑指offer14
剑指offer14:链表中倒数第K个结点 题目描述题目描述 输入一个链表,输出该链表中倒数第k个结点。 解法一:基于递归的方法class Solution { public: unsigned int cnt = 0; L
2020-05-11
  目录