一篇文章搞定面试中的链表题目(java实现)

废话少说，上链表的数据结构

classListNode{ListNodenext;intval;ListNode(intx){val=x;next=null;}}

1.翻转链表

ListNodereverse(ListNodenode){ListNodeprev=null;while(node!=null){ListNodetmp=node.next;node.next=prev;prev=node;node=tmp;}returnprev;}//翻转链表(递归方式)ListNodereverse2(ListNodehead){if(head.next==null){returnhead;}ListNodereverseNode=reverse2(head.next);head.next.next=head;head.next=null;returnreverseNode;}

2.判断链表是否有环

booleanhasCycle(ListNodehead){if(head==null||head.next==null){returnfalse;}ListNodeslow,fast;fast=head.next;slow=head;while(fast!=slow){if(fast==null||fast.next==null){returnfalse;}fast=fast.next.next;slow=slow.next;}returntrue;}

3,链表排序

ListNodesortList(ListNodehead){if(head==null||head.next==null){returnhead;}ListNodemid=middleNode(head);ListNoderight=sortList(mid.next);mid.next=null;ListNodeleft=sortList(head);returnmerge(left,right);}ListNodemiddleNode(ListNodehead){ListNodeslow=head;ListNodefast=head.next;while(fast!=null&fast.next!=null){slow=slow.next;fast=fast.next.next;}returnslow;}ListNodemerge(ListNoden1,ListNoden2){ListNodedummy=newListNode(0);ListNodenode=dummy;while(n1!=null&&n2!=null){if(n1.val<n2.val){node.next=n1;n1=n1.next;}else{node.next=n2;n2=n2.next;}node=node.next;}if(n1!=null){node.next=n1;}else{node.next=n2;}returndummy.next;}

4.链表相加求和

ListNodeaddLists(ListNodel1,ListNodel2){if(l1==null&&l2==null){returnnull;}ListNodehead=newListNode();ListNodepoint=head;intcarry=0;while(l1!=null&&l2!=null){intsum=carry+l1.val+l2.val;point.next=newListNode(sum%10);carry=sum/10;l1=l1.next;l2=l2.next;point=point.next;}while(l1!=null){intsum=carry+l1.val;point.next=newListNode(sum%10);carry=sum/10;l1=l1.next;point=point.next;}while(l2!=null){intsum=carry+l2.val;point.next=newListNode(sum%10);carry=sum/10;l2=l2.next;point=point.next;}if(carry!=0){point.next=newListNode(carry);}returnhead.next;}

5.得到链表倒数第n个节点

ListNodenthToLast(ListNodehead,intn){if(head==null||n<1){returnnull;}ListNodel1=head;ListNodel2=head;for(inti=0;i<n-1;i++){if(l2==null){returnnull;}l2=l2.next;}while(l2.next!=null){l1=l1.next;l2=l2.next;}returnl1;}

6.删除链表倒数第n个节点

ListNodedeletenthNode(ListNodehead,intn){// write your code hereif(n<=0){returnnull;}ListNodedumy=newListNode(0);dumy.next=head;ListNodeprdDel=dumy;for(inti=0;i<n;i++){if(head==null){returnnull;}head=head.next;}while(head!=null){head=head.next;prdDel=prdDel.next;}prdDel.next=prdDel.next.next;returndumy.next;}

7.删除链表中重复的元素

ListNodedeleteMuNode(ListNodehead){if(head==null){returnnull;}ListNodenode=head;while(node.next!=null){if(node.val==node.next.val){node.next=node.next.next;}else{node=node.next;}}returnhead;}

8.删除链表中重复的元素ii,去掉重复的节点

ListNodedeleteMuNode2(ListNodehead){if(head==null||head.next==null){returnhead;}ListNodedummy=newListNode(0);dummy.next=head;head=dummy;while(head.next!=null&&head.next.next!=null){if(head.next.val==head.next.next.val){intval=head.next.val;while(head.next.val==val&&head.next!=null){head.next=head.next.next;}}else{head=head.next;}}returndummy.next;}

9.旋转链表

ListNoderotateRight(ListNodehead,intk){if(head==null){returnnull;}intlength=getLength(head);k=k%length;ListNodedummy=newListNode(0);dummy.next=head;head=dummy;ListNodetail=dummy;for(inti=0;i<k;i++){head=head.next;}while(head.next!=null){head=head.next;tail=tail.next;}head.next=dummy.next;dummy.next=tail.next;tail.next=null;returndummy.next;}

10.重排链表

ListNodereOrder(ListNodehead){if(head==null||head.next==null){return;}ListNodemid=middleNode(head);ListNodetail=reverse(mid.next);mergeIndex(head,tail);}privatevoidmergeIndex(ListNodehead1,ListNodehead2){intindex=0;ListNodedummy=newListNode(0);while(head1!=null&&head2!=null){if(index%2==0){dummy.next=head1;head1=head1.next;}else{dummy.next=head2;head2=head2.next;}dummy=dummy.next;index++;}if(head1!=null){dummy.next=head1;}else{dummy.next=head2;}}

11.链表划分

ListNodepartition(ListNodehead,intx){if(head==null){returnnull;}ListNodeleft=newListNode(0);ListNoderight=newListNode(0);ListNodeleftDummy=left;ListNoderightDummy=right;while(head!=null){if(head.val<x){left.next=head;left=head;}else{right.next=head;right=head;}head=head.next;}left.next=rightDummy.next;right.next=null;returnleftDummy.next;}

12.翻转链表的n到m之间的节点

ListNodereverseN2M(ListNodehead,intm,intn){if(m>=n||head==null){returnhead;}ListNodedummy=newListNode(0);dummy.next=head;head=dummy;for(inti=1;i<m;i++){if(head==null){returnnull;}head=head.next;}ListNodepmNode=head;ListNodemNode=head.next;ListNodenNode=mNode;ListNodepnNode=mNode.next;for(inti=m;i<n;i++){if(pnNode==null){returnnull;}ListNodetmp=pnNode.next;pnNode.next=nNode;nNode=pnNode;pnNode=tmp;}pmNode.next=nNode;mNode.next=pnNode;returndummy.next;}

13.合并K个排序过的链表

ListNodemergeKListNode(ArrayList<ListNode>k){if(k.size()==0){returnnull;}returnmergeHelper(k,0,k.size()-1);}ListNodemergeHelper(List<ListNode>lists,intstart,intend){if(start==end){returnlists.get(start);}intmid=start+(end-start)/2;ListNodeleft=mergeHelper(lists,start,mid);ListNoderight=mergeHelper(lists,mid+1,end);returnmergeTwoLists(left,right);}ListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummy=newListNode(0);ListNodetail=dummy;while(list1!=null&&list2!=null){if(list1.val<list2.val){tail.next=list1;tail=tail.next;list1=list1.next;}else{tail.next=list2;tail=list2;list2=list2.next;}}if(list1!=null){tail.next=list1;}else{tail.next=list2;}returndummy.next;}

进群：697699179可以获取Java各类入门学习资料！

这是我的微信公众号【编程study】各位大佬有空可以关注下，每天更新Java学习方法，感谢！

学习中遇到问题有不明白的地方，推荐加小编Java学习群：697699179内有视频教程 ，直播课程 ，等学习资料，期待你的加入