剑指Offer——反转链表

Question

输入一个链表，反转链表后，输出链表的所有元素。

Solution

如果空间复杂度要求为O(1)的话，可以考虑用三个指针来进行反转
如果没有空间复杂度限制的话，可以考虑用一个栈，将节点全部push到栈用，然后再生成新的链表。

Code

/*

struct ListNode {

	int val;

	struct ListNode *next;

	ListNode(int x) :

			val(x), next(NULL) {

	}

};*/

class Solution {

public:

	// 就地完成反转

    ListNode* ReverseList(ListNode* pHead) {

		ListNode* pre = NULL;

        ListNode* head = pHead;

        ListNode* next = head;

        while (next) {

            next = head->next;

            head->next = pre;

            pre = head;

            if (next)

                head = next;

        }

        return head;

    }

    // O(n)的空间

    ListNode* ReverseList(ListNode* pHead) {

        if (pHead == NULL)

            return NULL;

        stack<ListNode*> stack1;

        ListNode* tmp = pHead;

        while (tmp) {

            stack1.push(tmp);

            tmp = tmp->next;

        }

        ListNode* first = new ListNode(-1);

        pHead = first;

        while (!stack1.empty()) {

            ListNode* current = stack1.top();

            stack1.pop();

            first->next = current;

            first = current;

        }

        first->next = NULL;

        return pHead->next;

    }

};

巴特西

剑指Offer——反转链表

Question

Solution

Code

最新文章

热门文章