找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 4913|回复: 0

Lintcode451 Swap Nodes in Pairs solution 题解

0

主题

0

帖子

0

积分

贫民

积分
0
锖青磁 发表于 2018-6-3 18:40:30 | 显示全部楼层 |阅读模式
本帖最后由 锖青磁 于 2018-6-3 18:45 编辑

【题目描述】
Given a linked list, swap every two adjacent nodes and return its head.
给一个链表,两两交换其中的节点,然后返回交换后的链表。

【题目解析】
这道题考察了基本的链表操作,注意当改变指针连接时,要用一个临时指针指向原来的next值,否则链表丢链,无法找到下一个值。
本题的解题方法是:
需要运用fakehead来指向原指针头,防止丢链,用两个指针,ptr1始终指向需要交换的pair的前面一个node,ptr2始终指向需要交换的pair的第一个node。
然后就是进行链表交换。
需要用一个临时指针nextstart, 指向下一个需要交换的pair的第一个node,保证下一次交换的正确进行。
然后就进行正常的链表交换,和指针挪动就好。
当链表长度为奇数时,ptr2.next可能为null;
当链表长度为偶数时,ptr2可能为null。
所以把这两个情况作为终止条件,在while判断就好,最后返回fakehead.next。










回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表