一、题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
二、代码及思路
思路：
我想建立一个临时节点用来存储。
根据上面的流程继续前行。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { ListNode pre = new ListNode(-1,head); ListNode cur = pre; while(cur.next != null && cur.next.next != null){ ListNode temp = head.next.next; cur.next = head.next; head.next.next = head; head.next = temp; cur = head; head = head.next; } return pre.next; } }
其他大神解法
//递归 class Solution { public ListNode swapPairs(ListNode head) { //终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表 if(head == null || head.next == null){ return head; } //一共三个节点:head, next, swapPairs(next.next) //下面的任务便是交换这3个节点中的前两个节点 ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; //根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分 return next; } }
- 时间复杂度：O ( n ) O(n)O(n)
- 空间复杂度：O ( 1 ) O(1)O(1)
