LintCode 532: Reverse Pairs
2024-08-28 21:25:18
LintCode 35: Reverse Linked List
题目描述
翻转一个链表。
样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null。
Thu Sep 21 2017
思路
本题的思路很多，今天把之前的方法改进了一下，使用两个指针就可以达到目的了（实际上也用了三个指针，但之前的方法太繁琐了）。
翻转链表的本质是将原本的“箭头”反转，这个操作在只有两个元素的时候很好实现，就一条赋值语句即可。而到了多个元素的时候，只需多考虑一下怎么暂存指针地址，避免链表“断掉”后找不到节点的情况就行了。
代码
// 反转链表
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The new head of reversed linked list.
*/
ListNode* reverse(ListNode* head)
{
ListNode* pNewHead;
if (head == NULL || head->next == NULL) return head;
ListNode *p1 = head, *p2 = head->next;
while (p2 != NULL)
{
ListNode* p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
pNewHead = p1;
head->next = NULL;
return pNewHead;
}
};
Mon Mar 6 2017
思路
这道题的方法就很多了，我这里第一想到的就是用三个指针来实现，可能我以前这么实现过吧。
不过这个方法并不是最优的方法，还可以用两个指针，或者递归实现，这些坑以后再补吧。
代码
// 反转链表
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The new head of reversed linked list.
*/
ListNode *reverse(ListNode *head) {
ListNode* ans;
if (head == NULL || head->next == NULL) return head;
else if (head->next->next == NULL)
{
head->next->next = head;
ans = head->next;
head->next = NULL;
return ans;
}
ListNode *p1 = head, *p2, *p3;
while(1)
{
p2 = p1->next;
p1 =
}
}
ListNode *reverse(ListNode *head) {
ListNode* ans;
if (head == NULL || head->next == NULL) return head;
else if (head->next->next == NULL)
{
head->next->next = head;
ans = head->next;
head->next = NULL;
return ans;
}
ListNode* p1 = head, *p2 = NULL, *p3 = NULL;
while(1)
{
if (p1 != NULL && p1->next != NULL && p1->next->next != NULL)
{
p2 = p1->next;
p1->next = p3;
p3 = p2->next;
p2->next = p1;
p1 = p3->next;
p3->next = p2;
continue;
}
else if (p1 != NULL && p1->next != NULL && p1->next->next == NULL)
{
ans = p1->next;
ans->next = p1;
p1->next = p3;
}
else if (p1 != NULL && p1->next == NULL)
{
ans = p1;
ans->next = p3;
}
else
{
ans = p3;
}
break;
}
head->next = NULL;
return ans;
}
};
最新文章
- 公司的一个面试题：如何用css让一个容器水平垂直居中？
- C#编程总结--总目录
- Nodejs与ES6系列2:Promise对象
- nginx rewrite 指令last break区别最详细的解释
- IOC框架的认识
- POJ 2249
- 为什么JS动态生成的input标签在后台有时候没法获取到
- COJ 1002 WZJ的数据结构（二）（splay模板）
- python之路-pip安装
- Oracle 快照及 dblink使用 （两台服务器数据同步）
- 最简单的视频编码器：基于libx265（编码YUV为H.265）
- 【Egret】在WebStorm里使用Egret Engine 的注意点
- Apriori算法(C#)
- Spring+SpringMVC+MyBatis+easyUI整合进阶篇(一)设计一套好的RESTful API
- 【git】idea /git bash命令 操作分支
- Confluence 6 配置管理员会话的安全
- 洛谷 P3627 [APIO2009]抢掠计划
- 【python】json中字典key不可为数值型
- Oracle 控制文件管理
- 使用DDOS deflate抵御少量DDOS攻击