题解 | #反转链表#

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if (pHead == nullptr) {
			return nullptr;
		}
		ListNode * pre = nullptr;
		ListNode * now = pHead;
		ListNode * next = nullptr;

		while (now != nullptr) {
			next = now->next;
			now->next = pre;
			pre = now;
			now = next;
		}

		return pre;
    }
};

单链表反转,一般都是通过多个指针辅助,将节点的next指针指向前一个节点。关键在于当前节点如果直接改变了next指针的指向,则会丢失掉该节点next指针原本指向的节点,故所以需要借助额外的临时指针变量保存原本的next指向的节点。

还有另外一种实现,利用递归实现反转链表:

node* ReverseList(node* pHead) {

    if (pHead == nullptr || pHead->next == nullptr)

        return pHead;

   

    node * temp = ReverseList(pHead->next);

    pHead->next->next = pHead;

    pHead->next = nullptr;

    return temp;

}

传入头节点,通过递归返回最后一个节点的地址,然后在递归函数中一个个将节点的next指向反转

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务