给定一个单链表的头结点pHead,长度为n,反转该链表后,返回新链表的表头。
数据范围: nleq1000n≤1000
要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
示例1输入:
{1,2,3}
返回值:
{3,2,1}示例2
输入:
{}
返回值:
{}
说明:
空链表则输出空代码:
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead==NULL)return NULL; ListNode* t=new ListNode(-1); ListNode* p1=pHead; ListNode* p2=p1->next; if(p2==NULL)return pHead; ListNode* p3=p2->next; if(p3==NULL) { t=p2; t->next=p1; p1->next=NULL; return t; } ListNode* g; p2->next=p1; p1->next=NULL; while(p3!=NULL){ g=p3->next; p3->next=p2; p2=p3; p3=g; } t=p2; return t; } };解题思路:
就是把每个结点的next改成前一个结点,注意特殊例子就行。
头结点直接是第一个点,不是空结点。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)