Leetcode 328 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
实现策略：
创建两个单链表，一个链表用于存放奇数点，一个链表用于存放偶数点，之后将奇数链的最后一个节点与偶数链的第一个节点相连接即可。
public ListNode oddEvenList(ListNode head) {
if(head==null || head.next==null)
{
return head;
}
// 创建两个新的空链表
ListNode odd=new ListNode(0);
ListNode oddfirst=odd;
ListNode even=new ListNode(0);
ListNode evenfirst=even;
int i=0;
while(head!=null){
i++;
if(i%2==1){
ListNode oddcurr=new ListNode(head.val);
odd.next=oddcurr;
odd=oddcurr;
}
else{
ListNode evencurr=new ListNode(head.val);
even.next=evencurr;
even=evencurr;
}
head=head.next;
}
// 将奇数链的最后一个节点与偶数链的第一个节点进行相连
odd.next=evenfirst.next;
evenfirst.next=null;
return oddfirst.next;
}
Leetcode 2: 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
实现思路：
/*
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
*
* */
/*
* 分析：这里面存在几个问题：
*l1与l2等长的时候；以及l1与l2不等长的情况
*
* */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null && l2==null){
return null;
}
ListNode result=new ListNode(0);
ListNode first=result;
int flag=0;
while(l1!=null && l2!=null){
int sum=l1.val+l2.val+flag;
flag=0;
ListNode current=new ListNode(sum%10);
result.next=current;
result=current;
if(sum>9){
flag=1;
}
l1=l1.next;
l2=l2.next;
}
if(l1==null){
while(l2!=null){
int sum=l2.val+flag;
flag=0;
if(sum>9){
flag=1;
}
ListNode current=new ListNode(sum%10);
result.next=current;
result=current;
l2=l2.next;
}
}
if(l2==null){
while(l1!=null){
int sum=l1.val+flag;
flag=0;
if(sum>9){
flag=1;
}
ListNode current=new ListNode(sum%10);
result.next=current;
result=current;
l1=l1.next;
}
}
if(flag==1){
ListNode flagnode=new ListNode(flag);
result.next=flagnode;
}
return first.next;
}
小结一个点：
头插链表：
有三个节点：
节点1------节点2-----节点3------.......
（head） (prev) (cur)
实现代码：
prev.next=cur.next;
cur.next=head.next;
head.next=cur;
cur.next=prev.next;
注意其顺序，方便记忆。
应用1：反转链表使用头插法进行：（由于head节点不空，可以声明一个-1节点，使其指向head节点，作为上面的head节点）：
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
if(head.next==null){
return head;
}
ListNode empty=new ListNode(-1);
empty.next=head;
ListNode cur=head.next;
while(cur!=null){
head.next=cur.next;
cur.next=empty.next;
empty.next=cur;
cur=head.next;
}
return empty.next;
}
应用2：Leetcode 92： 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
实现策略：
设置一个新的节点，指向链表头结点，将m到n之间元素按照上述策略进行头插操作。返回声明节点的next节点即可。
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode prev=dummy;
for(int i=0;i<m-1;i++){
prev=prev.next;
}
ListNode head2=prev;
prev=head2.next;
ListNode cur=prev.next;
for(int i=m;i<n;i++){
prev.next=cur.next;
cur.next=head2.next;
head2.next=cur;
cur=prev.next;
}
return dummy.next;
}
Leetcode 86： 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
实现原理：类似于之前奇偶链表，创建两个链表min和max，最后进行拼接即可。
public ListNode partition(ListNode head, int x) {
if(head==null){
return null;
}
// 创建两个链表头
ListNode min=new ListNode (-1);
ListNode result=min;
ListNode max=new ListNode(-1);
ListNode maxpre=max;
while(head!=null){
if(head.val<x){
ListNode mincur=new ListNode(head.val);
min.next=mincur;
min=mincur;
}
else{
ListNode maxcur=new ListNode(head.val);
max.next=maxcur;
max=maxcur;
}
head=head.next;
}
// 实现拼接
min.next=maxpre.next;
maxpre.next=null;
return result.next;
}
Leetcode 83 ： 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
实现原理：注意这里的链表是初始有序的。创建一个新的链表，current记录当前元素的值，由于链表有序，如果当前节点的值大于current，则直接更新current，否则就继续。
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return null;
ListNode result=new ListNode(-1);
ListNode prev=result;
int current = Integer.MIN_VALUE;
while(head!=null){
if(head.val!=current){
ListNode node=new ListNode(head.val);
result.next=node;
result=node;
current=head.val;
}
head=head.next;
}
return prev.next;
}
Leetcode 82: 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
实现原理：相较于I，这里设置了两个指针点，prev与cur，cur表示的是当前节点位置，prev保证其之前的元素是结果元素。
加了一重循环，找到第一个合适的cur点，将prev的指针指向cur点。
public ListNode deleteDuplicates2(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode result=new ListNode(-1);
result.next=head;
ListNode prev=result;
ListNode cur=head;
while(cur!=null && cur.next!=null)
{
if(cur.val!=cur.next.val){
prev=cur;
cur=cur.next;
}
else{
while(cur.next!=null && cur.val==cur.next.val){
cur=cur.next;
}
prev.next=cur.next;
cur=cur.next;
}
}
return result.next;
}