题目描述
给定一个链表,两两交换其中相邻的节点(结点进行交换而不是简单地进行值交换),并返回交换后的链表。
示例:
输入:1->2->3->4
输出:2->1->4->3
解析
实现技巧:递归实现
实现方法
如果利用调整指针的方式完成链表的交换会产生大量的指针交换操作,难度较大。
这里介绍递归实现:
- 链表每次交换前两个结点
- 后面n-2个结点作为新的链表递归实现
- n-2结点的结果放到前两个结点的链表后面
递归实现代码
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){//递归判断条件,如果无结点或者只有一个结点直接返回
return head;
}
/*取出前两个结点*/
ListNode first = head;
ListNode second = head.next;
/*head指向新的链表*/
head = second.next;
/*前两个结点交换位置*/
second.next = first;
/*head链表的结果链接到前两个结点链表后面*/
first.next = swapPairs(head);
/*返回结果*/
return second;
}