leetcode24：两两交换链表中的节点

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
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) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现

    递归交换：
        定义一个递归函数，该函数每次交换链表中的前两个结点，
        然后递归地对剩余的链表进行同样的操作。
    交换操作：
        在递归函数中，需要保存下一个要交换的结点，然后交换当前的两个结点。
        交换操作可以通过改变结点的 next 指针来完成。
    递归的终止条件：
        如果链表为空或只有一个结点，则无需交换，直接返回当前结点。
    
    时间复杂度：O(n)
        其中 n 是链表的结点数量。对每个结点进行更新指针的操作。
    空间复杂度：O(n)
        递归调用会使用到栈空间，其空间复杂度取决于链表的长度。
*/
class Solution_0 {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};

/*
    迭代实现
    
    时间复杂度：O(n)
        其中 n 是链表的结点数量。
    空间复杂度：O(1)
        仅使用常数的额外空间。
*/
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        for (ListNode* p = dummy; p->next && p->next->next; ) {
            ListNode *node1 = p->next, *node2 = p->next->next;
            p->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            p = node1;
        }

        return dummy->next;
        // ListNode* res = dummy->next;
        // delete dummy;
        // return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, 4};

    // 创建链表
    ListNode* head = createList(nums);

    // 交换操作
    ListNode* result = solution.swapPairs(head);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    deleteList(result);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表结点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    递归实现
    处理当前的两个结点进行交换，然后对后续的结点递归调用该函数继续交换。
    
    时间复杂度：O(n)
        其中 n 是链表的结点数量。需要对每个结点进行更新指针的操作。
    空间复杂度：O(n)
        主要取决于递归调用的栈空间。
*/
func swapPairs_0(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := head.Next
    head.Next = swapPairs(newHead.Next)
    newHead.Next = head
    return newHead
}

/*
    设置一个哑结点作为新的表头，使用一个指针 prev 来记录每对要交换结点的前一个结点。
    每次循环找到当前的两个结点进行交换操作，即让 prev 的下一个结点变为第二个结点，
    第一个结点指向原来第二个结点的下一个结点，第二个结点指向第一个结点，
    然后更新 prev 为第一个结点，继续向后推进。
    
    时间复杂度：O(n)
        仅遍历一遍所有结点。
    空间复杂度：O(1)
        仅使用常数的额外空间。
*/
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{-1, head}
    cur := dummyHead

    // 遍历链表，两两交换节点
    for cur.Next != nil && cur.Next.Next != nil {
        // 定义需要交换的两个节点
        node1 := cur.Next
        node2 := cur.Next.Next

        // 交换节点
        cur.Next = node2
        node1.Next = node2.Next
        node2.Next = node1

        // 移动到下一组需要交换的节点
        cur = node1
    }

    return dummyHead.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        head    []int
        expected []int
    }{
        {
            head:     []int{1,2,3,4},
            expected: []int{2,1,4,3},
        },
        {
            head:     []int{},
            expected: []int{},
        },
        {
            head:     []int{1},
            expected: []int{1},
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.head)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
        result := swapPairs(head)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}