Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

leetcode腾讯精选练习之链表逆置(三)

人生也疯狂 2020-01-14 21:25:00 阅读数:53 评论数:0 点赞数:0 收藏数:0

反转单链表

题目:

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路:

1.定义一个结点指针pCur指向当前链表,再定义一个指针pPre指向前一个结点,初始化为NULL。
2.循环遍历该链表,定义一个临时指针pNext指向当前链表的下一个结点,然后断开当前结点和下一个结点的指针关系,让当前结点的指针pCur的next指向pPre,即完成当前结点的反转。然后前移pPre指针和pCur指针,循环顺序执行该操作。
3.当临时指针pNext为NULL的时候说明pCur指针已经走到该链表的最后一个结点

代码:

ListNode* reverseList(ListNode* head) {
ListNode* pPre = NULL;
ListNode* pCur = head;
while (pCur != NULL)
{
ListNode* pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
if (pNext == NULL)
{
return pCur;
}
pCur = pNext;
}
return pCur;
}

改进版:

ListNode* reverseList(ListNode* head) {
ListNode* pPre = NULL;
ListNode* pCur = head;
ListNode* pNext =NULL;
while (pCur != NULL)
{
pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
}
return pPre;
}

总结:

1.思路很简单就是指针交换确定好指针交换的顺序就行
2.改进版本的思路还是一样,只是减少了判断的次数,数据量大的时候时间节约比较明显,小数据量差距不大。

纸上得来终觉浅,绝知此事要躬行

版权声明
本文为[人生也疯狂]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/zh20130424/p/12194173.html