关于java:LeetCode024两两交换链表中的节点

40次阅读

共计 1148 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容：给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。

你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：双指针法

首先，如果 head 为空或者 head 没有后继节点，间接返回 head；

而后用 2 个指针 first 和 second 别离指向第一个和第二个节点，new 一个 pre 节点指向 first，操作过程如下：

first 的 next 指向 second 的 next；

second 的 next 指向 first；

pre 的 next 指向 second；

后面几步就是把 first 和 second 的地位替换；

而后 pre 指向 first；

first 指向 first 的 next；

而后进行下一次遍历，条件是 first 不为空且 first 的 next 不为空，直到这个条件不成立，则遍历完结。

返回后果。

public class LeetCode_024 {public static ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}
        ListNode newHead = head.next;
        ListNode pre = new ListNode(-1), first = head, second;
        pre.next = head;
        while (first != null && first.next != null) {
            second = first.next;

            first.next = second.next;
            second.next = first;
            pre.next = second;

            pre = first;
            first = first.next;
        }

        return newHead;
    }

    public static void main(String[] args) {ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = swapPairs(head);
        while (result != null) {System.out.print(result.val + " ");
            result = result.next;
        }
    }
}