新博文地址:[leetcode]Swap Nodes in Pairs
http://oj.leetcode.com/problems/swap-nodes-in-pairs/
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.
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.
转换相邻节点的前后次序
要求:空间复杂度O(1),不能改变ListNode的值
好吧,暂时无视这些要求:
1. 如果可以改变ListNode的值,程序会非常简单:直接交换节点与后继节点的值即可
public ListNode swapPairsWithModifyValues(ListNode head) { ListNode tail = head; while (tail != null) { if (tail.next != null) { int tem = tail.val; tail.val = tail.next.val; tail.next.val = tem; tail = tail.next.next; } else { break; } } return head; }
2. 如果可以分配空间,需要借助栈来实现,也是相当简单的:(由于只需要转置2个节点,因此栈空间开到2就可以了)
public ListNode swapPairsWithExtraSpace(ListNode head) { if (head == null) { return null; } Stack stack = new Stack<ListNode>(); ListNode tail = head; ListNode newHead = new ListNode(0); ListNode newTail = newHead; while (tail != null) { stack.push(tail); tail = tail.next; if (tail != null) { stack.push(tail); tail = tail.next; newTail.next = new ListNode(((ListNode) stack.pop()).val); newTail = newTail.next; } newTail.next = new ListNode(((ListNode) stack.pop()).val); newTail = newTail.next; } return newHead.next; }
3. 无空间,不修改节点值的做法,需要维护四个指针,这个大家画个图就出来了,解释起来比较麻烦。。。(太没节操了。。。)
public ListNode swapPairs(ListNode head) { if (head == null) { return null; } ListNode preHead = new ListNode(0, head); ListNode node = head.next; ListNode prePre = preHead; ListNode pre = head; while (node != null) { ListNode post = node.next; node.next = pre; pre.next = post; prePre.next = node; if(post == null){ break; } prePre = pre; node = post.next; pre = post; if(node == null){ break; } post = node.next; } return preHead.next; }
相关推荐
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays...24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
LeetCode题目Largest Rectangle in Histogram 解答
leetcode 答案解析 golang解答
Swap Nodes in Pairs Spiral Matrix Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
leetcode下载 Algorithm 每日一题 && 天天进步一点点 题目来于 LeetCode,剑指offer,Coding Interview,ZOJ,POJ 等平台。 欢迎Coders对代码加以指正和提议!...Nodes in Pairs 练习: leetcode: 237. D
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Leetcode Solutions in Rust, Advent of Code Solutions in Ru
algorithm templates and leetcode examples in Python3, you
leetcode 锈leetcode_in_rust 用 Rust 编写的 LeetCode 练习
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案
leetcode中文版
vs code LeetCode 插件
in Java 本项目是我对 上的问题的所有解答。LeetCode 是一个为准备 IT 面试的 OJ 平台,上面有非常丰富且高质量的问题。这里所有的解答都使用的 Java,并且你可以将本项目直接导入到 Eclipse 中。 每一道题都附带了 ...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
24:swap-nodes-in-pairs 漂亮的递归解决方案 25: reverse-nodes-in-k-group: 解析 pre_for_next 到辅助函数 29:除以两个整数:溢出; 两反 31:下一个排列:再做一次(排序!) 32:最长有效(),使用栈,左推idx ...
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: ...快速开始产品特点登入/登出 只需在LeetCode Explorer单击“ Sign in to LeetCode , LeetCode Explorer使用LeetC
大佬的leetcode刷题笔记(c++版本)
100个leetCode详细解答