LeetCode 206:Reverse Linked List

zhihua_bupt

于 2015-12-11 11:21:42 发布

阅读量685

点赞数 1

分类专栏： LeetCode C++ DataStructure&Algorithms LeetCode算法分析

本文链接：https://blog.csdn.net/geekmanong/article/details/50261321

版权

C++ 同时被 3 个专栏收录

133 篇文章

订阅专栏

DataStructure&Algorithms

131 篇文章

订阅专栏

LeetCode算法分析

128 篇文章

订阅专栏

Reverse a singly linked list.

一、题目描述

翻转单链表

二、解题思路

利用两个结点指针和一个中间结点指针temp(用来记录当前结点的下一个节点的位置)，分别指向当前结点和前一个结点，每次循环让当前结点的指针域指向前一个结点即可，翻转结束后，记得将最后一个节点的链域置为空。

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (head == NULL || head->next == NULL) return head;
		ListNode* prev=head;
		ListNode* cur=head->next;
		ListNode* temp=head->next->next;
		while (cur){
			temp = cur->next; //temp作为中间节点，记录当前结点的下一个节点的位置
			cur->next = prev;  //当前结点指向前一个节点
			prev= cur;     //指针后移
			cur = temp;  //指针后移，处理下一个节点
		}

		head->next = NULL; //while结束后，将翻转后的最后一个节点（即翻转前的第一个结点head）的链域置为NULL
		return prev;
	}
};