两两交换链表中的节点

两两交换链表中的节点

题目描述

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

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

示例

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

解题

思路

先定义一个虚拟头节点（因为我要要操作第一个元素的话，得拥有第一个元素前面的引用，否则会很麻烦，所以，我们用虚拟头节点，这也是链表操作中常用的手段）。

我们应该隔一个操作交换一次位置，所以要用到除2取余大法，来确认我们的交换动作，隔一次一执行。

交换的时候是交换前面节点的后面两个节点，所以他后面的节点和后面的后面的节点都不能为空。

因为1->2->3 交换完了应该是 2->1->3。

然后交换四部操作，即可完成两两互换。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
         // 循环次数
        int loopCount = 0;
        // 虚拟头节点
        ListNode first = new ListNode(-1);
        first.next = head;

        ListNode result = first;
        while (first != null) {

            if (loopCount % 2 == 0 && first.next != null && first.next.next != null) {
                ListNode temp = first.next;
                first.next = first.next.next;
                temp.next = first.next.next;
                first.next.next = temp;
            }

            loopCount++;
            first = first.next;
        }

        return result.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

leetcode展示