注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex24 Swap Nodes in Pairs  

2015-05-15 21:36:27|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目说的是相邻的两个链表上元素交差,但是不能改变值,而且是线性空间复杂度内要完成。

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

刚一看,貌似要求有点儿高,其实细想了一下,也没有什么难度,关键我还自己想到了一个好的处理链表头的好方法,就是开始的时候在链表头加一个节点,这样原来的头就有前缀了,好多关于head难处理的问题都解决了,最后出来的时候再把加的头删掉就行了,感觉不错。见c代码

struct ListNode* traverse(struct ListNode*head)
{
if (head == NULL || head->next == NULL)
{
return NULL;
}
if (head->next->next == NULL)
{
return head->next; //返回current的下一个节点
}
struct ListNode*current = NULL, *p1 = NULL, *p2 = NULL,*p3 = NULL;
current = head;

p1 = current->next;
p2 = p1->next;
p3 = p2->next;
current->next = p2;
p2->next = p1;
p1->next = p3;
return p2;
}
struct ListNode* swapPairs(struct ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
struct ListNode* current=NULL,*p=NULL;
p = (struct ListNode*)malloc(sizeof(struct ListNode));

p->val = -1;
p->next = head;
head = p;

current = head;
while (current != NULL)
{
p = traverse(current);
current->next = p;
if (p==NULL||p->next == NULL || p->next->next == NULL)
{
break;
}
current = current->next->next;
}

p = head;
head = head->next;
free(p);
p = NULL;
return head;
}


second time 精简代码

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
return traverse(head);
}
ListNode* traverse(ListNode*head)
{
ListNode * fake = new ListNode(INT_MIN);
ListNode * current=NULL,*p1=NULL,*p2=NULL,*tmp=NULL;
fake->next = head;
head = fake;
current = head;
while (current->next != NULL&&current->next->next != NULL)
{
tmp = current->next->next->next;
p2 = current->next->next;
p1 = current->next;
p2->next = p1;
p1->next = tmp;
current->next = p2;
current = current->next->next;
}
fake = head;
head = head->next;
delete fake;
return head;
}
};


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017