导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-24.Swap Nodes in Pairs

题目

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1 -> 2 -> 3 -> 4 , you should return the list as 2 -> 1 -> 4 -> 3 .

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

翻译

给出一个单链表,交换每两个相邻节点,并返回头结点。
例如,给出 1 -> 2 -> 3 -> 4 ,应当返回 2 -> 1 -> 4 -> 3
你的算法应当只使用常数空间。你能修改list中的值,只能改变节点。

画图很清晰,每次交换两个节点,需要注意的是,交换完两个节点后,后面节点的后继,要指向下两个节点交换后的在前面的节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode left = head, right = head.next;
head = right;
while (true) {
left.next = right.next;
right.next = left;
left = left.next;
if (left == null || left.next == null) return head;
right = right.next;
right.next = left.next;
right = left.next;
}
}
}