LeetCode刷题实战24:两两交换链表中的节点
程序IT圈
共 1399字,需浏览 3分钟
·
2020-08-30 18:55
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做两两交换链表中的节点,我们先来看题面:
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed.
题意
样例
给定 1->2->3->4
, 你应该返回2->1->4->3
.
题解
从链表的头节点 head 开始递归。
每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点,则继续递归。
交换了两个节点以后,返回 secondNode,因为它是交换后的新头。
在所有节点交换完成以后,我们返回交换后的头,实际上是原始链表的第二个节点。
class Solution {
public ListNode swapPairs(ListNode head) {
// If the list has no node or has only one node left.
if ((head == null) || (head.next == null)) {
return head;
}
// Nodes to be swapped
ListNode firstNode = head;
ListNode secondNode = head.next;
// Swapping
firstNode.next = swapPairs(secondNode.next);
secondNode.next = firstNode;
// Now the head is the second node
return secondNode;
}
}
上期推文:
评论