你今天学算法了吗?打卡第十二天
目录
一、题目
1、题目描述
2、基础框架
3、原题链接
二、解题报告
1、思路分析
2、代码详解
3.代码注释
三、本题小知识
一、题目
1、题目描述
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
示例 2:
输入:head = [2,1], x = 2
输出:[1,2]
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 partition(ListNode head, int x) {}
提示:
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
3、原题链接
LeetCode 86. 分隔链表
二、解题报告
1、思路分析
使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
- 对链表进行一遍遍历,定义两个链表,
- 一个存放小于特殊值X的结点,一个存放大于特殊值的结点
- 最后将放小于特殊值X的链表的尾节点next指向放大于特殊值链表的头节点
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 partition(ListNode head, int x) { //定义存放小于特定值x的链表 ListNode little = new ListNode(0); //定义结点存放小于的头节点 ListNode littleHead = little; //定义链表存放大于特定值x的链表 ListNode big = new ListNode(0); //定义结点存放大于的链表头节点 ListNode bigHead = big; //遍历链表 while(head!=null){ if(head.val<x){ //(1) little.next=head; little=little.next; }else{//(2) big.next = head; big=big.next; } //指针后移,继续向后遍历 head=head.next; } big.next=null; little.next=bigHead.next;//(3) return littleHead.next; }}
3.代码注释
(1)小于特殊值X的结点放入链表little
(2)大于特殊值X的结点放入链表big
(3)将放小于特殊值X的链表的尾节点next指向放大于特殊值链表的头节点
三、本题小知识
链表 数据结构