JZ15 反转链表

本文最后更新于：2022年4月9日 中午

image-20211006105801872

Solution

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == nullptr || pHead->next==nullptr){
            return pHead;
        }
        ListNode* rHead = ReverseList(pHead->next);
        pHead->next->next = pHead;
        pHead->next = nullptr;
        return rHead;
    }
};
  • 迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == nullptr || pHead->next==nullptr){
            return pHead;
        }
        ListNode* pre=NULL, *cur=pHead;
        while(cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};