百度&必应权4, 日IP8000. 查看详情
自助收录

24. 两两交换链表中的节点(解法一:循环迭代)

算法刷题2年前 (2023)更新 江南白衣
351 0 0
24. 两两交换链表中的节点(解法一:循环迭代)

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

24. 两两交换链表中的节点(解法一:循环迭代)
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
分析:
建议使用虚拟头结点,这样就不用考虑头结点的问题,会方便很多。接下来就是交换相邻两个元素了,这个时候一定要画画草图,如果不画图,操作多个指针的时候很容易混乱,尤其是要操作的先后顺序。
初始时,cur指向虚拟头结点,然后进行如下三步:

24. 两两交换链表中的节点(解法一:循环迭代)

看这个可能就更直观一些了:

24. 两两交换链表中的节点(解法一:循环迭代)

时间复杂度:O(n)
空间复杂度:O(1)

package com.codernav.demo.leetcode.linkedlist.swapPairs;

import com.codernav.demo.common.ListNode;

/**
 * @title 24. 两两交换链表中的节点(迭代)
 * @Description 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。
 * 你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/4
 */
public class Q_24_1 {
    public static void main(String[] args) {
        ListNode node4 = new ListNode(4, null);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // 迭代
        ListNode node = swapPairs(node1);
        System.out.println(node);
    }

    public static ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head,这样方面后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点,保存两个节点后面的节点
        ListNode firstnode; // 临时节点,保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点,保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动,准备下一轮交换
        }
        return dumyhead.next;
    }

}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...