知乎ID: 码蹄疾 

码蹄疾，毕业于哈尔滨工业大学。 

小米广告第三代广告引擎的设计者、开发者； 

负责小米应用商店、日历、开屏广告业务线研发；

主导小米广告引擎多个模块重构； 

关注推荐、搜索、广告领域相关知识;

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

分析

两两合并节点，头结点的两个节点合并后，剩下的又可以转化为两两合并的子问题，所以递归求解即可。

code

/** * 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 left = head;        ListNode right = head.next;        left.next = swapPairs(right.next);        right.next = left;        return right;    }}

 

  微信扫码关注公众号，获得第一手新鲜资料！