java 成对交换节点

rur96b6h 于 2023-02-18 发布在 Java

关注(0)|答案(1)|浏览(147)

我正在尝试解决以下leetcode问题：
给定一个链表，每两个相邻节点交换一次并返回链表头，你必须在不修改链表节点值的情况下解决这个问题（也就是说，只有节点本身可以被修改）。
例如：输入：磁头=[1，2，3，4]输出：[二、一、四、三]
我是一个新手，以链表，并已写了以下代码为上述问题：

public void swapPairs() {
        if(head == null || head.next == null) {
            return;
        }

        Node prev = head;
        Node firstNode = head;
        Node secondNode = head.next;

        while(secondNode != null) {
            Node nxt = secondNode.next;

            prev.next = secondNode;
            firstNode.next = nxt;
            secondNode.next= firstNode;

            if(nxt == null) {
                break;
            }

            prev = firstNode;
            firstNode = nxt;
            secondNode = firstNode.next;
        }

    }

上面代码返回的输出是[1，4，3]。我不明白为什么2没有出现在列表的开头。

Java

来源：https://stackoverflow.com/questions/75453179/swapping-nodes-in-pairs

1条答案

按热度按时间

9gm1akwq1#

您的代码将正确执行成对交换，但head引用从未更新，但很明显，在此成对交换之后，头部现在应该是原始排序中的第二个节点。
因此，在循环之前添加这一行：

head = head.next;

可视化可能会有所帮助，让我们以输入列表1，2，3，4为例：

head
  ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 2   │   │ data: 3   │   │ data: 4   │
│ next: ──────► │ next: ──────► │ next: ──────► │ next: null│
│           │   │           │   │           │   │           │
└───────────┘   └───────────┘   └───────────┘   └───────────┘

使用您的代码更新next引用后，我们将得到：

head
  ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ data: 1   │   │ data: 2   │   │ data: 3   │   │ data: 4   │
│ next: ┐   │   │ next: ┐   │   │ next: null│   │ next: ┐   │
│       │   │◄──────────┘   │   │           │◄──────────┘   │
└───────│───┘   └───────────┘   └───────────┘ ┌►└───────────┘
        └─────────────────────────────────────┘

节点已经按照预期重新连接，如果我们从第二个节点开始，沿着箭头（next引用），我们可以看到节点按照期望的顺序链接，但是，因为head仍然引用值为1的节点，所以我们不会再看到值为2的节点，因为它现在的顺序在该节点之前。
因此，在重新布线过程开始之前，我们应该使head引用值为2的节点。

赞(0）回复(0）举报 2023-02-18

我来回答

java 成对交换节点

1条答案

相关问题

热门标签

最新问答