问题描述:
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.
原问题链接:https://leetcode.com/problems/swap-nodes-in-pairs/
问题分析
这个问题看起来比较简单,主要是要对里面的实现细节考虑清楚了。我们可以结合一个图来考虑。
假定我们有这么一个链表,我们首先设定它们要交换的两个元素分别为first, second。
因为要交换first, second, 所以首先将first.next赋值给second.next:
然后再将first.next指向second:
由上图很明显,我们还需要调整pre引用,使得pre.next = first:
上面的描述是针对某个时候节点调整的细节。不过既然前面要求是对整个链表里每两个相邻的元素都这么调整。那么这里必然是用一个循环来处理。在每个循环的开始,我们将pre.next赋值给second,pre.next.next赋值给first。因为链表里元素可能有奇数个或者偶数个元素,我们可以将pre.next != null && pre.next.next != null作为循环跳出的条件。
这样,作为一个完整的循环。我们会在每个循环的开始将pre.next, pre.next.next分别赋值给second和first。同时在调整结束后将pre设置为second的值。这样方便在下一个循环继续调整。
按照前面的讨论,详细实现的代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNode temp = new ListNode(0); temp.next = head; ListNode pre = temp, first = null, second = null; while(pre.next != null && pre.next.next != null) { first = pre.next.next; second = pre.next; second.next = first.next; first.next = second; pre.next = first; pre = second; } return temp.next; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
Algorithm-In-Leetcode To solve algorithm problems in leetcode.com using Python, Golang and SQL It's my leetcode account: 这是我的LeetCode中文账户: 不仅仅是Algorithm,还有Database的题目也包含在内。题目...
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode:LeetCode题解