1.删除链表中的重复元素2
82. 删除排序链表中的重复元素 II - 力扣(LeetCode)
给定一个已排序的链表的头 head
, 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
class Solution {public ListNode deleteDuplicates(ListNode head) {if(head==null){return head;}ListNode dummy=new ListNode(0,head);ListNode cur=dummy;while(cur.next!=null&&cur.next.next!=null){if(cur.next.val==cur.next.next.val){int x=cur.next.val;while(cur.next!=null&&cur.next.val==x){cur.next=cur.next.next;}}else{cur=cur.next;}}return dummy.next;}
}
2.删除链表中的重复元素
给定一个已排序的链表的头 head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
83. 删除排序链表中的重复元素 - 力扣(LeetCode)
class Solution {public ListNode deleteDuplicates(ListNode head) {if(head==null){return head;}ListNode cur=head;while(cur.next!=null){if(cur.val==cur.next.val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}
}
3.分隔链表
86. 分隔链表 - 力扣(LeetCode)
给你一个链表的头节点
head
和一个特定值x
,请你对链表进行分隔,使得所有 小于x
的节点都出现在 大于或等于x
的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
方法一:模拟
class Solution {public ListNode partition(ListNode head, int x) {ListNode small=new ListNode(0);ListNode smallHead=small;ListNode large=new ListNode(0);ListNode largeHead=large;while(head!=null){if(head.val<x){small.next=head;small=small.next;}else{large.next=head;large=large.next;}head=head.next;}large.next=null;small.next=largeHead.next;return smallHead.next;}
}
4.合并两个有序数组
88. 合并两个有序数组 - 力扣(LeetCode)
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int currentIndex = m + n - 1;int nums1Index = m-1;int nums2Index = n-1;while (nums1Index>=0) {int num1 = nums1[nums1Index--];while (nums2Index >= 0 && num1 < nums2[nums2Index]) {nums1[currentIndex] = nums2[nums2Index];nums2Index--;currentIndex--;}nums1[currentIndex] = num1;currentIndex--;}while (nums2Index>=0) {nums1[currentIndex--] = nums2[nums2Index--];}}
}
5.格雷编码
n 位格雷码序列 是一个由
2n
个整数组成的序列,其中:
- 每个整数都在范围
[0, 2n - 1]
内(含0
和2n - 1
)- 第一个整数是
0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ,且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数
n
,返回任一有效的 n 位格雷码序列 。
方法一:归纳法
class Solution {public List<Integer> grayCode(int n) {List<Integer> ret = new ArrayList<Integer>();ret.add(0);for (int i = 1; i <= n; i++) {int m = ret.size();for (int j = m - 1; j >= 0; j--) {ret.add(ret.get(j) | (1 << (i - 1)));}}return ret;}
}
方法二:公式法
class Solution {public List<Integer> grayCode(int n) {List<Integer> ret = new ArrayList<Integer>();for (int i = 0; i < 1 << n; i++) {ret.add((i >> 1) ^ i);}return ret;}
}