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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目：

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

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

示例:

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

解题思路：

设置三个指针，分别指向前后和当前节点。

首先设置创建一个prehead结点，用来返回结果。

接着创建left、mid、right三个结点，交换mid和right结点的位置，然后修改left结点的next值。

最后使left等于修改后的mid结点（实际上是left、mid、right三个节点中最右位置的结点，因为交换了mid、right结点的位置），mid =left.next，right = mid.next

class Solution {

    public ListNode swapPairs(ListNode head) {

        if(head == null)

            return head;

        ListNode prehead = new  ListNode(-1);

        prehead.next = head;

        ListNode left = prehead;

        ListNode mid = prehead.next;

        ListNode right = mid.next;

        while(mid != null && right != null)

        {

            mid.next = right.next;

            right.next = mid;

            left.next = right;

            left = mid;

            mid = left.next;

            if(mid != null) //如果mid为空，则需判断一下

                right = mid.next;

        }

        return prehead.next;

    }

}