leetcode每日刷题之链表篇(二)奇偶链表,移除重复节点
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
今天刷了一些感觉挺有趣的链表题,从明天开始打算刷一些树的题,祝我可以一次AC。
一、奇偶链表
题目描述:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
题目解析:这个题大体思路还算比较好想,但是要想没有bug的话,还是需要花费一些精力的。我的想法是首先排除空的链表,然后分别把两个奇数位链表放到奇数位的链表里,偶数链表放到偶数位链表里。最后再接上。
代码说明:
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;//判断空链表进行排除
ListNode odd = head;//奇数位链表的头部
ListNode even = odd.next;//偶数位链表的头部
ListNode evenhead = even;//用来定位偶数位链表的头部,后期进行连接
//这一块的作用就是,判断两位和三位以及更多的情况
while(even!=null&&even.next!=null){
//剩下的四行代码就是将奇数位放到奇数位数组,偶数位放到偶数位数组
odd.next = even.next;
odd=odd.next;
even.next = odd.next;
even=even.next;
}
//拼接
odd.next=evenhead;
return head;
}
}
二、移除重复节点
题目描述:编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3]
示例2:
输入:[1, 1, 1, 1, 2]
输出:[1, 2]
提示:
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶:
如果不得使用临时缓冲区,该怎么解决?
题目解析:我看到这个题的第一想法是用hashset做,主要想法遍历链表,然后和hashset进行对比,包含的话就删除,不包含就存进去,直至最后
代码说明:
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
//定义一个hashset表
HashSet<Integer> set =new HashSet<>();
//临时头节点
ListNode temp = new ListNode(-1);
temp.next = head;
ListNode pre = temp;
while(pre.next!=null){
//是否包含该节点
if(set.contains(pre.next.val)){
pre.next=pre.next.next;
}
else{
set.add(pre.next.val);
pre=pre.next;
}
}
return temp.next;
}
}
总结
奇偶链表那个题代码量不多,但是实现的时候挺多错误,需要认真思考。