24.两两交换链表中的节点

题目描述

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
img
1
输入:head = [1,2,3,4]
2
输出:[2,1,4,3]
Copied!
示例 2:
1
输入:head = []
2
输出:[]
Copied!
示例 3:
1
输入:head = [1]
2
输出:[1]
Copied!
提示:
    链表中节点的数目在范围 [0, 100]
    0 <= Node.val <= 100
进阶:你能在不修改链表节点值的情况下解决这个问题吗?(也就是说,仅修改节点本身。)

题解

方法一:递归

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode swapPairs(ListNode head) {
13
if(head == null||head.next == null) return head;
14
ListNode newHead = head.next;
15
head.next = swapPairs(newHead.next);
16
newHead.next = head;
17
return newHead;
18
}
19
}
Copied!

方法二:迭代

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode swapPairs(ListNode head) {
13
if(head == null || head.next == null) return head;
14
ListNode dummyNode = new ListNode(0);
15
dummyNode.next = head;
16
ListNode tmp = dummyNode;
17
while(tmp.next!=null&&tmp.next.next!=null){
18
ListNode node1 = tmp.next;
19
ListNode node2 = node1.next;
20
tmp.next = node2;
21
node1.next = node2.next;
22
node2.next = node1;
23
tmp = node1;
24
}
25
return dummyNode.next;
26
}
27
}
Copied!
最近更新 4mo ago