您现在的位置是:首页 >其他 >LeetCode链表题(中等)剖析网站首页其他
LeetCode链表题(中等)剖析
?文章导读
?文章作者:?噢!刺激
本篇文章主要对5道LeetCode上链表中等的题做了一下分析,欢迎大家知错,本篇文章收于专栏;?图解LeetCode
?文章专栏:?JavaSE语法、?图解LeetCode、?数据结构剖析
?1.合并零之间的结点
解题思路
解题思路:
1、想要把零之间的节点值全部加起来并且把所有的零节点都删除掉,肯定是需要知道头节点的位置的,所以定义head1用来记录头节点的位置
2、记录好头节点位置后,在定义一个cur来遍历所有的节点,再用一个变量sum来专门对值不是0的节点进行相加,
3、当cur遍历到值是0的节点时,就停止遍历,将head1所在的节点中的值设置为sum,再将里面所存的地址变为cur里面存的下一个 节点的地址,这样就把一小段两个0之间的不为0的节点和最后一个0节点给删除掉了,之后cur向后移动一个结点,把head1在移到cur的位置,这样就又开始一小段节点的遍历。
4、直到cur走完这个链表,循环终止
public ListNode mergeNodes(ListNode head) {
ListNode cur = head.next;
ListNode head1 = head;
int sum = 0;
while(cur != null){
while(cur.val != 0) {
sum+=cur.val;
cur = cur.next;
}
if(cur != null) {
head1.val = sum;
head1.next = cur.next;
cur = cur.next;
head1 = cur;
sum = 0;
}
}
return head;
}
?2.链表中最大孪生和
解题思路
第一种解题方法:
这一道题不用返回节点,只是单纯的找最大值,所以可以把这一道题转化成顺序表来做。先把这个节点里的值都加入到顺序表中,顺便记录一下有多少个值,之后就简单了,根据题目要求就是对顺序表中的值进行访问了,最后找出最大值!
public int pairSum(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode cur = head;
int count = 0;
//将节点中的值假如到顺序表中
while(cur != null) {
list.add(cur.val);
cur = cur.next;
//计算有多少个节点
count++;
}
int result = 0;
for(int i = 0; i <= count/2-1; i++) {
//找出i下标所对应的值加上它的孪生值
int c = list.get(i) + list.get(count-1-i);
//比较
result = Math.max(result,c);
}
return result;
}
?3.链表的随机节点
解题思路
解题思路:
第一种方法:利用顺序表存储每一个值
利用顺序表存储所有的节点值,然后随机在顺序表中选择一个节点值,这样的方法比较花费内存,因为在存储所有节点时,要遍历所有的节点,假设有n个节点的话,所以初始化时,时间复杂度为O(n),随机选择时,时间复杂度为O(1),而要在顺序表中存储每个节点,所以空间复杂度也是O(n).
class Solution {
List<Integer> list;
Random random;
public Solution(ListNode head) {
//用一个顺序表来记录链表里的值
list = new ArrayList();
while(head != null) {
list.add(head.val);
head = head.next;
}
random = new Random();
}
public int getRandom() {
//生成随机数
int x = random.nextInt(list.size());
return list.get(x);
}
}
第二种方法:蓄水池抽样算法:
因为题目要求是随机抽取一个节点,而每个节点的概率都必须相等,所以遍历每个节点,当遍历第一个节点时,生成[0,1)的随机数,第一个节点被选中的概率就是1/1;第一个节点一定会被选中,所以先将答案值设置成第一个节点的值,当遍历第二个节点时,生成[0,2)的随机数,所以前两个节点被选中的概率分别是1/2;当遍历到第三个节点时,生成[0,3)之间的随机数,所以前三个节点每个节点被选中的概率是1/3,而又如何知道当前的节点是否被选中呢?因为,第一个节点已经被设置成了答案值,所以,当生成的是0时,就表示当前节点被选中了,然后把答案值设置成当前节点的值,但是为什么是0呢?而不是1或者其他呢?因为,如果是1的话,当遍历第一个节点时,是不可能生成1的,就导致每个节点没选中的概率不一样,而如果是0的话,当遍历到第n个结点时,前面的每个节点被选中的概率都是1/n;
初始化时,不需要遍历所有节点,所以时间复杂度为O(1),随机抽取时,要遍历所有的节点,所以时间复杂度为O(n),而空间复杂度的话只需要存储一个值,所以是O(1)
class Solution {
Random random;
ListNode head;
//初始化
public Solution(ListNode head) {
random = new Random();
this.head = head;
}
public int getRandom() {
int i = 1;
int ans = 0;
ListNode cur = head;
while(cur!= null) {
if(random.nextInt(i)==0) {
ans = cur.val;
}
i++;
cur = cur.next;
}
return ans;
}
}
?4.复杂链表的复制
解题思路
解题思路:
如下图所示,创建三个节点分别插入在每个节点的后面,通过三个循环最后完成节点的复制;
第一个循环:分别将三个目标节点插入到每个节点后面
第二个循环:将目标节点中random的指向与源节点中的指向匹配
第三个循环:最后将目标节点中的next连接起来,生成一个新的链表
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
for(Node cur = head; cur != null; cur = cur.next.next) {
Node NodeNew = new Node(cur.val);
NodeNew.next = cur.next;
cur.next = NodeNew;
}
for(Node cur = head; cur != null; cur = cur.next.next) {
Node randomNew = cur.next;
randomNew.random = (cur.random != null) ? cur.random.next : null;
}
Node headNew = head.next;
for(Node cur = head; cur != null; cur = cur.next) {
Node newCur = cur.next;
cur.next = cur.next.next;
newCur.next = (newCur.next == null) ? null : newCur.next.next;
}
return headNew;
}
?5.两辆交换两表中的节点
解题思路
解题方法:
定义两个快慢指针,快指针比慢指针差一个节点的距离,两个指针分别向后走两个节点,然后交换两个节点中的值,这里要注意,因为是走两个节点,所以要注意越界的问题,当快指针的next等于null了时候,快指针就不要向后走了,所以就避免了越界问题
public ListNode swapPairs(ListNode head) {
if(head == null) {
return null;
}
//定义两个快慢指针
ListNode slow = head;
ListNode fast = head.next;
while(slow != null && fast!=null) {
//交换两个值
int x = slow.val;
slow.val = fast.val;
fast.val = x;
//两指针向后走两步
slow = slow.next.next;
//判断快指针的next
if(fast.next != null){
fast = fast.next.next;
}
}
return head;
}