你今天学算法了吗?打卡第九天
目录
一、题目
1、题目描述
2、基础框架
3、原题链接
二、解题报告
1、思路分析
2、代码详解
三、本题小知识
一、题目
1、题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
2、基础框架
Java 版本给出的基础框架代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapPairs(ListNode head) { }}
3、原题链接
LeetCode 24. 两两交换链表中的节点
二、解题报告
1、思路分析
(1)用 head 表示原始链表的头节点,新的链表的第二个节点,
(2)用 newHead 表示新的链表的头节点,原始链表的第二个节点,
(3)原始链表中的其余节点的头节点是 newHead.next。
(4)令 head.next = swapPairs(newHead.next),表示将其余节点进行两两交换,交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head,即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
2、代码详解
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapPairs(ListNode head) { //如果链表为空或者只有一个结点则无法交换直接返回 if(head==null||head.next==null){ return head; } //定义结点newHead表示第二个结点和交换后的头节点 ListNode newHead=head.next; /** *交换其他结点 *newHead.next为头节点 */ //交换后的头节点为head.next head.next=swapPairs(newHead.next); //交换后的第二个结点为head newHead.next=head; return newHead; }}
三、本题小知识
链表交换