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

题目地址(24. 两两交换链表中的节点)

https://leetcode.cn/problems/swap-nodes-in-pairs/

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]

前置知识

公司

• 暂无

思路

关键点

• 指针确保要更新正确

代码

• 语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }

        ListNode newHead = head.next;

        // 这里设置了四个指针，比较繁琐
       // prev 前驱，first/second两个要交换的指针，next，后继指针
        ListNode prev = null;
        ListNode first = head;
        ListNode second = head.next;
        ListNode next = second.next;
        while (first != null && second != null) {
            if (prev != null) {
                prev.next = second;
            }
            second.next = first;
            first.next = next;
            prev = first;
            first = next;
            if (first == null) {
                break;
            }
            second = first.next;
            if (null == second) {
                break;
            }
            next = second.next;

        }
        return newHead;
    }
}

使用哑结点的简便写法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 这里只需更新两个节点prev 和 first
        ListNode prev = dummyHead;
        ListNode current = head;
        while(current != null && current.next != null) {
            // 另两个节点second和next在循环里面更新即可
            ListNode second = current.next;
            ListNode next = second.next;
            prev.next = second;
            second.next = current;
            current.next = next;

            prev = current;
            current = next;
        }
        return dummyHead.next;
    }
}

Go Code

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 这种直接获取引用的写法，注意初始化时，这里是大括号{}
    dummyHead := &ListNode{0, head}
    prev, first := dummyHead, head
    for first != nil && first.Next != nil {
        second, next := first.Next, first.Next.Next
        prev.Next = second
        second.Next = first
        first.Next = next

        prev = first
        first = next
    }
    return dummyHead.Next
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：