原链表有序，去掉重复的保留所有不同的如：1, 2, 2 1, 2（Leetcode2276）
思路：
-
最low的就是使用俩while循环，一个指向固定的值譬如m，另一个从m的下一个节点开始扫描，如果遇到和m相同的节点就过滤掉，但leetcode官方居然把这种方式作为进阶！！！我不理解真的。。。
-
利用HashSet的不重复性进行去重：
public ListNode removeDuplicateNodes(ListNode head){ if(head==null){ return null; } Sethad = new HashSet (); ListNode newNode = head; had.add(head.val); while (head.next!=null){ if(had.contains(head.next.val)){ head.next=head.next.next; }else { head = head.next; } } return newNode; } -
上面方法的递归版：
递归：只考虑当前节点应该做的事 ->
若当前节点在set中出现过 抛弃 下一个节点调用递归方法
若当前节点在set中未出现过 添加到set中 该节点的下一个节点为(下一个节点调用递归方法)
返回头结点class Solution { Setset = new HashSet<>(); public ListNode removeDuplicateNodes(ListNode head) { if(head == null) return null; if(set.contains(head.val)){ return removeDuplicateNodes(head.next); } set.add(head.val); head.next = removeDuplicateNodes(head.next); return head; } } -
然后我还看到有大佬使用位运算来解决的，不得不说有点东西，我运行了一下，发现这种方式运行时间是我的一半，同时内存消耗也比我的小，思路其实本质上还是使用一个表存储已经出现过的值，将数组bits中每个数看成二进制就容易理解了。固定模m，则任意一个整数x，都可以表示为 x = k*m + b。代码中m=32，即任意一个值val都由k和b唯一确定。
- 代码中bits[cur.val / 32] |= 1 << (cur.val % 32)就是记录当前cur.val，（cur.val = k*m + b，m=32。 故cur.val / 32 = k ， b = cur.val % 32，1 << b就是为了记录b的位置。这样的话一个数就可由 【数组下标k】+【k对应的元素的二进制位b】唯一确定。）
- 数组bits[k]的二进制表达的第b位为1，则表示值为k*32+b的数已经出现过
- if里面就是判断，cur.next的值是否出现过。
- 若出现则&结果不为0，跳过cur的下一个节点
- 若没出现&结果为0，链表接上
public ListNode removeDuplicateNodes(ListNode head) { int[] bits = new int[20000 / 32 + 1]; ListNode cur = head; while (cur != null && cur.next != null) { bits[cur.val / 32] |= 1 << (cur.val % 32); if ((bits[cur.next.val / 32] & (1 << (cur.next.val % 32))) != 0) cur.next = cur.next.next; else cur = cur.next; } return head; }
floyd（弗洛伊德）判圈算法
我们之前是利用Set的不重复性来判断链表是否有环的（详见上一篇博文），这次我可以使用这种快慢指针的方式来判断链表是否有环。
这种方法也叫龟兔赛跑法，其本质思路通俗来讲就是：两个人在操场上跑步，一个跑得慢一个跑得快，那么只要他们一直跑下去，终会有相遇的那刻，有一种“ta逃ta追ta插翅难飞”的赶脚。
弗洛伊德（Floyd ）使用了两个指针，一个慢指针（龟）每次前进一步，快指针（兔）指针每次前进两步（两步或多步效果是等价的，只要一个比另一个快就行。但是如果移动步数增加，算法的复杂度可能增加）。如果两者在链表头以外（不包含开始情况）的某一点相遇（即相等）了，那么说明链表有环，否则，如果（快指针）到达了链表的结尾（如果存在结尾，肯定无环），那么说明没环。
public boolean hasCycle(ListNode head) {
if (head==null||head.next==null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow!=fast){
if (fast.next==null||fast==null){//注意这块的判断条件
return false;
}
slow=slow.next;//慢指针一次走一步；
fast=fast.next.next;//快指针一次走两步；
}
return true;
}
- 时间复杂度：O(N)
- 空间复杂度：O(1)
回文链表
思路一：我们可以使用双指针来判断回文：
public boolean isPalindrome(ListNode head){
List vals = new ArrayList();
//将链表的值放入数组中
ListNode newList = head;
while (newList!=null){
vals.add(newList.val);
newList = newList.next;
}
//双指针
int front = 0;
int back = vals.size()-1;
while (front
时间复杂度空间复杂度都是O(N)
思路二：可以利用上面讲过的快慢指针来避免使用O(N)的额外空间
整个流程可以分为以下五个步骤：
- 找到前半部分链表的尾节点。
- 反转后半部分链表（之前的博客有关于反转链表的思路）。
- 判断是否回文。
- 恢复链表。
- 返回结果。
代码：
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
今日推歌
-----《九月底》（悄咪咪庆祝一下国庆假期哈哈）
每当我想起你
在这秋风里
在这九月底
陪你走过四季
每当我又问询
关于你的消息
我想的事情
是你~~~
祝祖国母亲生日快乐！
祝大家国庆假期愉快~~~
