给定一个链表, 两两交换其中相邻的节点, 并返回交换后的链表.
你不能只是单纯的改变节点内部的值, 而是需要实际的进行节点交换.
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
链接: https://leetcode-cn.com/problems/swap-nodes-in-pairs
- /**
- * Definition for singly-linked list.
- * public class ListNode {
- * int val;
- * ListNode next;
- * ListNode(int x) { val = x; }
- * }
- */
- class Solution {
- public ListNode swapPairs(ListNode head) {
- if(head == null || head.next == null){
- return head;
- }
- ListNode next = head.next;
- head.next = swapPairs(next.next);
- next.next = head;
- return next;
- }
- }
这里的递归方式怎么理解呢, 其实就是从后往前了, 比如当满足递归的结束条件的时候, head.next = end, 然后执行递归下面的语句 next.next = head, 实际上就是执行了一次 end = head, 当然这里的 head 指的只是 end 前面的节点, 并不是起始节点 head, 然后继续弹栈直到结束.
非递归方式
- class Solution {
- public ListNode swapPairs(ListNode head) {
- ListNode pre = new ListNode(0);
- pre.next = head;
- ListNode temp = pre;
- while(temp.next != null && temp.next.next != null) {
- ListNode start = temp.next;
- ListNode end = temp.next.next;
- temp.next = end;
- start.next = end.next;
- end.next = start;
- temp = start;
- }
- return pre.next;
- }
- }
就这道题的话, 还是递归合适一点, 否则没什么做的意义.
来源: http://www.bubuko.com/infodetail-3354874.html