• 欢迎来到莫知我哀的博客,日常不定时更新C++、C#、Unity、OpenGL、游戏开发相关文章。同步博客: CSDN
  • 网站左下角可以开启好听的背景音乐~~
  • 如果您觉得本博客很有看点,那么赶紧使用Ctrl+D 收藏吧

[LeetCode] 24. Swap Nodes in Pairs

算法练习 wahh 269次浏览 0个评论 扫描二维码

题目

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

Example:

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

Note:

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

 

题意

输入一个链表,交换两两相邻位置的节点。注意:程序额外使用的空间必须在常数级,不能交换节点值,只能交换节点。

 

分析

如果要时间最后的结果其实只需要交换节点的值,不用改变链表结构,是比较容易的。

然而题目不允许改变节点的值,也就是说需要将节点包括内部值看做一个整体两两进行交换。

思路,使用两个指针分别指向相邻两个节点,然后通过交换next值使得相邻两个节点交换位置,不过值得注意的是:

A->B->C->D

在交换A,B的时候我们将A指向C,B指向A,达到交换A,B目的:B->A->C->D

然后在继续交换C,D的时候我们会发现,A仍然指向的是C,此时由于是单链表无法修改前置指针。

所以在交换A,B的时候,我们不能将A->next改为B->next,而是改为B->next->next。

同样的,返回指针头部的时候不能使用原来的head指针,而是使用head->next。

不过在过程中我们需要注意指针为空的情况!!

 

代码

 


莫知我哀 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:[LeetCode] 24. Swap Nodes in Pairs
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
Title - Artist
0:00