public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode myHead=new ListNode(-1),last=myHead;
ListNode p=l1,q=l2;
int add=0;
while(p!=null||q!=null){
int sum=add+(p==null?0:p.val)+(q==null?0:q.val);
add=sum/10;
ListNode t=new ListNode(sum%10);//加入链表
last.next=t;
last=t;
if(p!=null)p=p.next;
if(q!=null)q=q.next;
}
if(add!=0){//最后的进位
ListNode t=new ListNode(add);
last.next=t;
last=t;
}
return myHead.next;
}
}
分析
我们可以利用两个指针同步后移，当后一个指针到达链表末尾时，前一个指针刚好指向待删除元素的前驱节点。
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode myHead=new ListNode(-1),p,q;
myHead.next=head;
p=myHead;
q=myHead;
while(n-->0){
q=q.next;
}
while(q.next!=null){
p=p.next;
q=q.next;
}
p.next=p.next.next;
return myHead.next;
}
}
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode myHead=new ListNode(-1),last=myHead,p,q,t;
p=l1;
q=l2;
while(p!=null||q!=null){
if(q==null||(p!=null&&p.val<=q.val)){//处理链表1的节点
t=p;
p=p.next;<img src="http://img.blog.csdn.net/20160731205700468?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
}else{//否则处理链表2的节点
t=q;
q=q.next;
}
t.next=null;//尾插
last.next=t;
last=t;
}
return myHead.next;
}
}
分析
这里涉及多个链表的合并，我们可以利用归并算法的思想，采用分治的思想，将问题进行划分。
递归版
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
doMergeLists(lists,0,lists.length-1);
return lists[0];
}
private void doMergeLists(ListNode[] lists ,int start,int end){
if(start>=end){
return;
}
int mid=start+(end-start)/2;
doMergeLists(lists,start,mid);
doMergeLists(lists,mid+1,end);
lists[start]=mergeTwoLists(lists[start],lists[mid+1]);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode myHead=new ListNode(-1),last=myHead,p,q,t;
p=l1;
q=l2;
while(p!=null||q!=null){
if(q==null||(p!=null&&p.val<=q.val)){
t=p;
p=p.next;
}else{
t=q;
q=q.next;
}
t.next=null;//尾插
last.next=t;
last=t;
}
return myHead.next;
}
}
迭代版
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n=lists.length;
if(n==0) return null;
int size=1;//跨度，2的幂（这样每次归并后的结果下次正好用上）
while(size<=n){
int first=0,second=first+size;
while(second<n){
lists[first]=mergeTwoLists(lists[first],lists[second]);
first=second+size;
second=first+size;
}
size<<=1;
}
return lists[0];
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode myHead=new ListNode(-1),last=myHead,p,q,t;
p=l1;
q=l2;
while(p!=null||q!=null){
if(q==null||(p!=null&&p.val<=q.val)){
t=p;
p=p.next;
}else{
t=q;
q=q.next;
}
t.next=null;//尾插
last.next=t;
last=t;
}
return myHead.next;
}
}
分析
如果可以修改链表节点的值，我们迭代节点时，每次将指针移动两个位置，并将指针随后两个节点的值进行交换。
但是题目限定了我们不能修改链表节点中的值，那么我们只能换一种思路，每两个节点我们当做一个链表进行逆转。
递归版
public class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null) return head;
return swapAsGroup(head,2);
}
private ListNode swapAsGroup(ListNode head,int k){
if(head==null) return head;
ListNode p=head;
int count=k;
while(count-->1&&p.next!=null){
p=p.next;
}
ListNode left=p.next;
ListNode end=head,start=p;
p.next=null;
reverseList(head);
end.next=swapAsGroup(left,k);
return start;
}
private ListNode reverseList(ListNode head){//头插入法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
}
迭代版
public ListNode swapPairs(ListNode head) {
if(head==null) return head;
return swapAsGroup(head,2);
}
private ListNode swapAsGroup(ListNode head,int k){
ListNode myHead=new ListNode(-1),p,q;
myHead.next=head;
p=myHead;//p为前驱节点
while(p!=null&&p.next!=null){
int count=k;
q=p;
while(count-->0&&q.next!=null){
q=q.next;
}//q指向该组元素的末尾元素
ListNode left=q.next;//left指向剩余的元素的开头
ListNode first=q,end=p.next; //记录逆转后的头和尾，就是逆转前的尾和头
q.next=null;
reverseList(p.next);//逆转分组
p.next=first;//重新将链表链接起来
end.next=left;
p=end;//更新前驱节点
}
return myHead.next;
}
private ListNode reverseList(ListNode head){//头插入法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
分析
我们上一题的算法，已经可以实现了根据分组大小逆转。但是，现在我们要保证末尾大小不足k的分组不进行逆转，我们只需要添加条件判断即可。
迭代版
private ListNode swapAsGroup(ListNode head,int k){
if(head==null) return head;
ListNode p=head;
int count=k;
while(count>1&&p.next!=null){
p=p.next;
count--;//只有后移了才减少
}
if(count!=1){
return head;
}//这里添加条件判断
ListNode left=p.next;
ListNode end=head,start=p;
p.next=null;
reverseList(head);
end.next=swapAsGroup(left,k);
return start;
}
递归版
private ListNode swapAsGroup(ListNode head,int k){
ListNode myHead=new ListNode(-1),p,q;
myHead.next=head;
p=myHead;//p为前驱节点
while(p!=null&&p.next!=null){
int count=k;
q=p;
while(count>0&&q.next!=null){
q=q.next;
count--;//只有移动了才减少
}//q指向该组元素的末尾元素
if(count!=0){//这里添加条件判断
break;
}
ListNode left=q.next;//left指向剩余的元素的开头
ListNode first=q,end=p.next; //记录逆转后的头和尾，就是逆转前的尾和头
q.next=null;
reverseList(p.next);//逆转分组
p.next=first;//重新将链表链接起来
end.next=left;
p=end;//更新前驱节点
}
return myHead.next;
}
分析
我们只需要找到倒数第K的元素的前驱节点，然后将倒数k个元素组成的链表整体转移到表头即可。
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
int n=0;
ListNode p=head;
while(p!=null){
p=p.next;
n++;
}
if(n==0||k==0||(k=k%n)==0){
return head;
}
ListNode myHead=new ListNode(-1),q;
myHead.next=head;
p=myHead;
q=myHead;
while(k>0){//先将q后移k步
q=q.next;
k--;
}
while(q.next!=null){//同步后移
p=p.next;
q=q.next;
}
q.next=myHead.next;
myHead.next=p.next;
p.next=null;
return myHead.next;
}
}
扩展
如果我们旋转的是数组的时候，按照上面的思路，就没有链表旋转这样方便了。将尾部元素移动到最前面时，我们不仅需要额外的存储空间缓存我们将要移动的元素，还需要将其余元素后移。不过，因为数组的随机存取特性，我们可以将整个数组逆转，然后将前k的元素和后n-k个元素分别逆转，最终也能得到结果。这里应该可以很好的体会到链表离散存储和数组顺序存储的特性，以及这些特性给各自带来的局限性和优点。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode myHead=new ListNode(-1),p=head;
myHead.next=head;
while(p!=null){
if(p.next==null){
break;
}else{
if(p.next.val!=p.val){
p=p.next;
}else{
p.next=p.next.next;
}
}
}
return myHead.next;
}
}
此外，我们还可以采用尾插法重新建立链表，对与链表尾节点的值相同的节点我们忽略掉。
public ListNode deleteDuplicates(ListNode head) {
ListNode myHead=new ListNode(-1),last=myHead,p,candidate,t;
p=head;
while(p!=null){
if(p.next==null||p.next.val!=p.val){//末尾或者只出现一次
t=p;
p=p.next;
t.next=null;
last.next=t;
last=t;
}else{
candidate=p;
while(p!=null&&p.val==candidate.val){
p=p.next;
}
}
}
return myHead.next;
}
分析
我们直接利用尾插法建立两个链表，最后再合并即可。
public class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallerHead=new ListNode(-1),smallerLast=smallerHead;
ListNode biggerHead=new ListNode(-1),biggerLast=biggerHead;
ListNode p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=null;
if(t.val<x){
smallerLast.next=t;
smallerLast=t;
}else{
biggerLast.next=t;
biggerLast=t;
}
}
smallerLast.next=biggerHead.next;
return smallerHead.next;
}
}
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m==n) return head;
ListNode myHead=new ListNode(-1),p,q;
myHead.next=head;
p=myHead;
int count=m;
while(count-->1){
p=p.next;
}//p后移m-1步，p指向逆转部分前驱节点
count=n-m+1;
q=p;
while(count-->0){//q后移n-m+1步，q指向逆转部分尾节点
q=q.next;
}
ListNode start=q,end=p.next,left=q.next;
//start表示逆转后的头，end表示逆转后的尾，left表示后续链表的头
q.next=null;//注意将链表断开再逆转
reverseList(p.next);
end.next=left;
p.next=start;
return myHead.next;
}
private ListNode reverseList(ListNode head){//头插入法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
}
分析
我们采用分治的思想，将问题进行划分为左右子树构建BST。
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
ListNode p=head;
int n=0;
while(p!=null){
p=p.next;
n++;
}
return buildBST(head,n);
}
private TreeNode buildBST(ListNode head,int length){
if(length==0)return null;
TreeNode root=new TreeNode(-1);
if(length==1){
root.val=head.val;
return root;
}
int index=1;
int mid=(1+length)/2;
ListNode midNode=head;
while(index<mid){
midNode=midNode.next;
index++;
}
root.val=midNode.val;
root.left=buildBST(head,mid-1);
root.right=buildBST(midNode.next,length-mid);
return root;
}
}
分析：
如果我们复制链表主体的时候复制随机指针，可能这时候随机指针指向的元素，我们还没有进行复制，因此比较繁琐。
我们可以先复制链表的主体部分，我们只需要使用尾插法即可。第二趟我们来复制随机指针，因为原来链表中的的随机指针指向原链表的节点这里不能直接复制，因此需要将指向原链表节点的指针映射到新链表的节点，因此需要利用哈希表建立这种映射关系。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode myHead=new RandomListNode(-1),last=myHead,p=head;
HashMap<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();
while(p!=null){//尾插入法
RandomListNode t=new RandomListNode(p.label);
map.put(p, t);//建立映射关系，便于随机指针的复制
last.next=t;
last=t;
p=p.next;
}
p=head;
while(p!=null){//复制随机指针
RandomListNode t=map.get(p);
if(p.random==null){
t.random=null;
}else{
t.random=map.get(p.random);
}
p=p.next;
}
return myHead.next;
}
}
分析
我们利用利用两个指针，一个每次往后移动一步，一个每次往后移动两步。如果任何一个指针为null，即到达链表末尾，返回false。否则，最终两个指针肯定会碰头（相等），返回true。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode p,q;
if(head==null||head.next==null){
return false;//空或者第一个节点没有后继节点
}
p=head;
q=head.next;
while(p!=q){
p=p.next;
if(p==null) return false;
q=q.next;
if(q==null) return false;
q=q.next;
if(q==null) return false;
//p和q都不为null
}
return true ;
}
}
分析
首先我们利用上题中的方法判定有没有环，如果没环直接返回null。如果有环，p指向环中的某一个节点。
现在我们考虑两个链表，链表1：从头节点到p的链表；链表2：p的后继节点到p的链表。
不难发现，链表1和链表2具有相同的尾节点，现在问题就退化成了：求两个链表的第一个公共节点。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode p,q,t;
if(head==null||head.next==null){
return null;//空或者第一个节点没有后继节点
}
p=head;
q=head.next;
while(p!=q){
p=p.next;
if(p==null) return null;
q=q.next;
if(q==null) return null;
q=q.next;
if(q==null) return null;
//p和q都不为null
}
//此时，p指向环中的某个节点
ListNode headOne=head,endOne=p;
ListNode headTwo=p.next,endTwo=p;
int lengthOne=1,lengthTwo=1;
p=headOne;
while(p!=endOne){
p=p.next;
lengthOne++;
}
q=headTwo;
while(q!=endTwo){
q=q.next;
lengthTwo++;
}
if(lengthOne<lengthTwo){//保证第一个链表比第二个链表长，方便后续处理
t=headOne;headOne=headTwo;headTwo=t;
int temp=lengthOne;lengthOne=lengthTwo;lengthTwo=temp;
}
p=headOne;
q=headTwo;
int count=lengthOne-lengthTwo;
while(count>0){//先把长链表的指针后移两个链表的长度差
p=p.next;
count--;
}
//指针同步后移
while(p!=q){
p=p.next;
q=q.next;
}
return p ;
}
}
分析
首先我们可以将链表划分为前后两部分，1->2->null和3->4->null，然后将后半部分链表逆转为4->3->null。
然后将两个链表中的元素交替取出并采用尾插法建表。
public class Solution {
public void reorderList(ListNode head) {
int n=0;
ListNode myHead=new ListNode(-1),last=myHead;
ListNode p=head,firstHead,secondHead,t;
while(p!=null){
p=p.next;
n++;
}
if(n<=2) return;
int preLength,postLength;
postLength=n/2;
preLength=n-postLength;
firstHead=head;
secondHead=head;
int count=preLength;
while(count>0){
secondHead=secondHead.next;
count--;
}
secondHead=reverseList(secondHead);//逆转后半段链表
count=postLength;
while(count>0){
t=firstHead;
firstHead=firstHead.next;
t.next=null;
last.next=t;
last=t;
t=secondHead;
secondHead=secondHead.next;
t.next=null;
last.next=t;
last=t;
count--;
}
if(preLength>postLength){//最后可能多的单独元素
t=firstHead;
t.next=null;
last.next=t;
last=t;
}
}
private ListNode reverseList(ListNode head){//头插入法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
}
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode myHead=new ListNode(-1);
ListNode p=head,t;
while(p!=null){
t=p;
p=p.next;
insertList(myHead,t);
}
return myHead.next;
}
private void insertList(ListNode myHead,ListNode t){
ListNode pre=myHead,post=myHead.next;
while(post!=null&&post.val<=t.val){
pre=post;
post=post.next;
}
t.next=post;
pre.next=t;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p=headA,q=headB,t;
int lengthA=0,lengthB=0;
while(p!=null){
lengthA++;
p=p.next;
}
while(q!=null){
lengthB++;
q=q.next;
}
if(lengthA<lengthB){//保证第一个链表比第二个长
int temp=lengthA;lengthA=lengthB;lengthB=temp;
t=headA;headA=headB;headB=t;
}
int count=lengthA-lengthB;
p=headA;
q=headB;
while(count>0){//指针对齐
p=p.next;
count--;
}
while(p!=q){//同步后移
p=p.next;
q=q.next;
}
return p;
}
}
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode myHead=new ListNode(-1),pre;
myHead.next=head;
pre=myHead;
while(pre.next!=null){
if(pre.next.val==val){
pre.next=pre.next.next;
}else{
pre=pre.next;
}
}
return myHead.next;
}
}
public class Solution {
public ListNode reverseList(ListNode head){//头插法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
}
分析
我们可以将链表拆分为两半，并将后半段逆转，接着只需要前半段和后半段对应元素是否相等即可。判定完后，将后半段恢复。
public class Solution {
public boolean isPalindrome(ListNode head) {
int n=0;
ListNode p=head,firstHead,secondHead,t,q,firstEnd=null;
while(p!=null){
p=p.next;
n++;
}
if(n<=1) return true;
int preLength,postLength;
postLength=n/2;
preLength=n-postLength;
firstHead=head;
secondHead=head;
int count=preLength;
while(count>0){
if(count==1){
firstEnd=secondHead;
}
secondHead=secondHead.next;
count--;
}
secondHead=reverseList(secondHead);//逆转后半段链表
p=firstHead;
q=secondHead;
count=postLength;
while(count>0){
if(p.val!=q.val){
return false;
}
p=p.next;
q=q.next;
count--;
}
firstEnd.next=reverseList(secondHead);//恢复链表后半段
return true;
}
private ListNode reverseList(ListNode head){//头插入法
ListNode myHead=new ListNode(-1),p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=myHead.next;
myHead.next=t;
}
return myHead.next;
}
}
分析
删除节点时，我们一般会找到该节点的前驱，然后让前驱节点的指针指向该节点的后继节点。但是，此处我们只知道当前节点，根据当前节点我们可以获取到后继节点。我们不可能找到前驱节点，怎么办呢？
我们只能采用偷梁换柱的方法，我们将后继节点的值赋给当前节点，现在我们只需要删除后继节点即可。
对于非尾节点，其必定有后继节点。
public class Solution {
public void deleteNode(ListNode node) {
node.val=node.next.val;
node.next=node.next.next;
}
}
分析
我们先将链表拆分为两个链表，再链接起来即可。
public class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode oddHead=new ListNode(-1),oddLast=oddHead;
ListNode evenHead=new ListNode(-1),evenLast=evenHead;
ListNode p=head,t;
while(p!=null){
t=p;
p=p.next;
t.next=null;
oddLast.next=t;
oddLast=t;
if(p==null) break;
t=p;
p=p.next;
t.next=null;
evenLast.next=t;
evenLast=t;
}
oddLast.next=evenHead.next;
return oddHead.next;
}
}