算法每日一练 (3)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (3)

两两交换链表中的节点

题目地址：两两交换链表中的节点

题目描述

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

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

解题思路

• 首先处理边界条件，根据题意两两交换链表节点，那么当链表中是空或者只有一个节点时，不需要任何处理，直接返回结果即可。
• 其次确定头节点，由于之前的判断可以明确链表中此时至少有两个节点，那么直接交换后，头节点固定就是第二个节点，那么创建结果指针变量，指向 head 节点的 next 节点，最终直接返回这个指针变量即可。
• 创建辅助指针变量，用于交换链表节点：
  • i 指向当前需要交换的第一个节点（初始为原头节点）。
  • j 指向当前需要交换的第二个节点（初始为原第二个节点）。
  • k 指向 j 的下一个节点，即下一次交换的第一个节点。
• 在 while 循环中进行节点的交换，需要注意的是：由于 k 指向 j 的下一个节点，即下一次交换的第一个节点 那么当 k 或者 k.next 是空的时候有两种情况：
  • k 指针指向的节点不存在，没有可交换的节点。
  • k.next 指针指向的节点不存在，只剩下最后一个节点，不需要再进行交换。
• 紧接着指针移动，更改链表节点位置：
  • 将 i 指向下一个交换对的第一个节点
  • 更新 i 为下一个交换对的第一个节点
  • 更新 j 为下一个交换对的第二个节点
  • 更新 k 为下一个交换对的第一个节点
• 当循环结束时，最终返回头指针即可。

解题代码

c/c++

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (!head || !head->next)
            return head;

        ListNode *h = head->next;
        ListNode *i = head, *j = h, *k = h->next;

        while (true)
        {
            j->next = i;
            if (!k || !k->next)
            {
                i->next = k;
                break;
            }

            i->next = k->next;
            i = k;
            j = k->next;
            k = j->next;
        }

        return head;
    }
};

golang

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	h := head.Next
	i, j, k := head, h, h.Next

	for {
		j.Next = i
		if k == nil || k.Next == nil {
			i.Next = k
			break
		}

		i.Next = k.Next
		i = k
		j = k.Next
		k = j.Next
	}

	return h
}

lua

local ListNode = {}

function ListNode:new(val, next)
    local obj = {}
    setmetatable(obj, self)
    self.__index = self
    obj.Val = val or 0
    obj.Next = next or nil
    return obj
end

local function swapPairs(head)
    if head == nil or head.Next == nil then
        return head
    end

    local h = head.Next
    local i, j, k = head, h, h.Next

    while true do
        j.Next = i
        if k == nil or k.Next == nil then
            i.Next = k
            break
        end

        i.Next = k.Next
        i = k
        j = k.Next
        k = j.Next
    end

    return h
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。