0°

一篇文章搞定面试中的链表

内容预览:
  • 始发于微信公众号: 程序员小乐 分享编程技能、互联网技术、生活感悟、...~
  • 废话少说,上链表的数据结构~
  • 欢迎投稿~

始发于微信公众号: 程序员小乐

分享编程技能、互联网技术、生活感悟、打造干货分享平台,将总结的技术、心得、经验分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “杨守乐” ,选择“置顶公众号”,第一时间送达!



最近总结了一下数据结构和算法的题目,这是第二篇文章,关于链表的,第一篇文章关于二叉树的参见()。

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

class ListNode {
   ListNode next;
   int val;
   ListNode(int x){
       val = x;
       next = null;
   }
}

1.翻转链表

ListNode reverse(ListNode node){
       ListNode prev = null;
       while(node!=null){
           ListNode tmp = node.next;
           node.next = prev;
           prev = node;
           node = tmp;
       }
       return prev;
   }
   //翻转链表(递归方式)
   ListNode reverse2(ListNode head){
       if(head.next == null){
           return head;
       }
       ListNode reverseNode = reverse2(head.next);
       head.next.next = head;
       head.next = null;
       return reverseNode;
   }

2.判断链表是否有环

    boolean hasCycle(ListNode head){
       if(head == null|| head.next == null){
           return false;
       }
       ListNode slow,fast;
       fast = head.next;
       slow = head;
       while(fast!=slow){
           if(fast==null||fast.next==null){
               return false;
           }
           fast = fast.next.next;
           slow = slow.next;
       }
       return true;
   }

3.链表排序

    ListNode sortList(ListNode head){
       if(head == null|| head.next == null){
           return head;
       }
       ListNode mid = middleNode(head);
       ListNode right = sortList(mid.next);
       mid.next = null;
       ListNode left = sortList(head);
       return merge(left, right);
   }
   ListNode middleNode(ListNode head){
       ListNode slow = head;
       ListNode fast = head.next;
       while(fast!=null&fast.next!=null){
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
   }
   ListNode merge(ListNode n1,ListNode n2){
       ListNode dummy = new ListNode(0);
       ListNode node = 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;
       }
       return dummy.next;
   }

4.链表相加求和

    ListNode addLists(ListNode l1,ListNode l2){
       if(l1==null&&l2==null){
           return null;
       }
       ListNode head = new ListNode();
       ListNode point = head;
       int carry = 0;
       while(l1!=null&&l2!=null){
           int sum = carry + l1.val + l2.val;
           point.next = new ListNode(sum%10);
           carry = sum/10;
           l1 = l1.next;
           l2 = l2.next;
           point = point.next;
       }
       while(l1!=null){
           int sum = carry + l1.val;
           point.next = new ListNode(sum%10);
           carry = sum/10;
           l1 = l1.next;
           point = point.next;
       }
       while(l2!=null){
           int sum = carry + l2.val;
           point.next = new ListNode(sum%10);
           carry = sum/10;
           l2 = l2.next;
           point = point.next;
       }
       if(carry!=0){
           point.next = new ListNode(carry);
       }
       return head.next;
   }

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

    ListNode nthToLast(ListNode head,int n ){
       if(head == null||n<1){
           return null;
       }
       ListNode l1 = head;
       ListNode l2 = head;
       for(int i = 0;i<n-1;i++){
           if(l2 == null){
               return null;
           }
           l2 = l2.next;
       }
       while(l2.next!=null){
           l1 = l1.next;
           l2 = l2.next;
       }
       return l1;
   }

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

    ListNode deletenthNode(ListNode head,int n){
       // write your code here
       if (n <= 0) {
           return null;
       }
       ListNode dumy = new ListNode(0);
       dumy.next = head;
       ListNode prdDel = dumy;
       for(int i = 0;i<n;i++){
           if(head==null){
               return null;
           }
           head = head.next;
       }
       while(head!=null){
           head = head.next;
           prdDel = prdDel.next;
       }
       prdDel.next = prdDel.next.next;
       return dumy.next;
   }

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

    ListNode deleteMuNode(ListNode head){
       if(head == null){
           return null;
       }
       ListNode node = head;
       while(node.next != null){
           if(node.val == node.next.val){
               node.next = node.next.next;
           }else{
               node = node.next;
           }
       }
       return head;
   }

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

    ListNode deleteMuNode2(ListNode head){
       if(head == null||head.next == null){
           return head;
       }
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       head = dummy;
       while(head.next!=null&&head.next.next!=null){
           if(head.next.val == head.next.next.val){
               int val = head.next.val;
               while(head.next.val == val&&head.next != null){
                   head.next = head.next.next;
               }
           }else{
               head = head.next;
           }
       }
       return dummy.next;
   }

9.旋转链表

    ListNode rotateRight(ListNode head,int k){
       if(head ==null){
           return null;
       }
       int length = getLength(head);
       k = k % length;
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       head = dummy;
       ListNode tail = dummy;
       for(int i = 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;
       return dummy.next;
   }

10.重排链表

    ListNode reOrder(ListNode head){
       if(head == null||head.next == null){
           return;
       }
       ListNode mid = middleNode(head);
       ListNode tail = reverse(mid.next);
       mergeIndex(head, tail);
   }
   private void mergeIndex(ListNode head1,ListNode head2){
       int index = 0;
       ListNode dummy = new ListNode(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.链表划分

    ListNode partition(ListNode head,int x){
       if(head == null){
           return null;
       }
       ListNode left = new ListNode(0);
       ListNode right = new ListNode(0);
       ListNode leftDummy = left;
       ListNode rightDummy = 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;
       return leftDummy.next;
   }

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

    ListNode reverseN2M(ListNode head,int m,int n){
       if(m>=n||head == null){
           return head;
       }
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       head = dummy;
       for(int i = 1;i<m;i++){
           if(head == null){
               return null;
           }
           head = head.next;
       }
       ListNode pmNode = head;
       ListNode mNode = head.next;
       ListNode nNode = mNode;
       ListNode pnNode = mNode.next;
       for(int i = m;i<n;i++){
           if(pnNode == null){
               return null;
           }
           ListNode tmp = pnNode.next;
           pnNode.next = nNode;
           nNode = pnNode;
           pnNode = tmp;
       }
       pmNode.next = nNode;
       mNode.next = pnNode;
       return dummy.next;
   }

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

    ListNode mergeKListNode(ArrayList<ListNode> k){
       if(k.size()==0){
           return null;
       }
       return mergeHelper(k,0,k.size()-1);
   }
   ListNode mergeHelper(List<ListNode> lists,int start,int end){
       if(start == end){
           return lists.get(start);
       }
       int mid = start + ( end - start )/2;
       ListNode left = mergeHelper(lists, start, mid);
       ListNode right = mergeHelper(lists, mid+1, end);
       return mergeTwoLists(left,right);
   }
   ListNode mergeTwoLists(ListNode list1,ListNode list2){
       ListNode dummy = new ListNode(0);
       ListNode tail = 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;
       }
       return dummy.next;
   }

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!

如何您想进技术群和大牛们交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:IOExceptioner

链接:https://www.jianshu.com/p/a64d1ef95980

著作权归作者所有。本文已获得授权。欢迎投稿。

每日英文

You would feel totally different when diffierent persons do the same thing for you because we always concern the person instead of the matter itself. 

不同的人,为你做同一件事,你会感到天壤之别。因为我们在意的,往往不是人做的事,而只是做事的人。

乐乐有话说

一路走来,我们在跌跌撞撞中学会了坚强;在起起落落中学会了安然;在繁华落寞中学会了面对;在红尘纷扰中学会了自持,渐渐明白,有些路,要用脚去走;有些路,要用心去走。

一篇文章搞定面试中的链表


推荐阅读







看完本文有收获?请转发分享给更多人
关注「杨守乐」,提升技能

以上就是:一篇文章搞定面试中的链表 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


系统运维
系统运维
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论