技术控

    今日:110| 主题:49431
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] LinkedList 简单算法题解析

[复制链接]
撩开树枝 发表于 2016-10-9 15:20:25
147 3

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
LinkedList 算法题大纲

  
       
  • 反转单链表   
  • 判断单链表是否是回文的   
  • 判断链表是否有环   
  • 移除单链表倒数第N个元素   
  • 合并两个排序的单链表   
  • 移除重复的元素从排序的链表当中   
  • 链表当中删除指定值的节点   
  • 删除当前链表节点   
  • 交换链表节点的位置  
  反转单链表

  反转一个单链表:
  a -> b -> c -> d 反转后
  d -> c -> b -> a
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.         //先在循环外设置个pre指针
  11.     //循环head,每次都吧当前head的next指向pre
  12.     //最后返回pre即可
  13.     public ListNode reverseList(ListNode head) {
  14.         ListNode pre = null;
  15.         while(head != null) {
  16.           ListNode tmp = head;
  17.           head = head.next;
  18.           tmp.next = pre;
  19.           pre = tmp;
  20.         }
  21.         return pre;
  22.     }
  23. }
复制代码
判断单链表是否是回文的

  回文单链表如下,简单的描述回文就是正向读和逆向读是一样的就是回文:
  1 -> 2 -> 3 -> 2 -> 1
  解题思想:
  
       
  • 利用快慢指针找到链表的中间元素   
  • 反转中间元素next后面是元素   
  • 比对head到中间元素以及中间元素到结尾是否相同  
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public boolean isPalindrome(ListNode head) {
  11.         if (head == null) {
  12.             return true;
  13.         }
  14.         ListNode slow = head;
  15.         ListNode fast = head;
  16.         while (fast.next != null && fast.next.next != null) {
  17.             slow = slow.next;
  18.             fast = fast.next.next;
  19.         }
  20.         ListNode aft = reverse(slow.next);
  21.         while(aft != null) {
  22.             if (head.val != aft.val) {
  23.                 return false;
  24.             }
  25.             head = head.next;
  26.             aft = aft.next;
  27.         }
  28.         return true;
  29.     }
  30.     private ListNode reverse(ListNode head) {
  31.        ListNode pre = null;
  32.        while(head != null) {
  33.            ListNode tmp = head;
  34.            head = head.next;
  35.            tmp.next = pre;
  36.            pre = tmp;
  37.        }
  38.        return pre;
  39.     }
  40. }
复制代码
判断链表是否有环

  解题思路:
  使用快慢指针解决
  1. /**
  2. * Definition for singly-linked list.
  3. * class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) {
  7. *         val = x;
  8. *         next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     public boolean hasCycle(ListNode head) {
  14.         if (head == null || head.next == null) {
  15.             return false;
  16.         }
  17.         ListNode fast = head.next;
  18.         ListNode slow = head;
  19.         while (fast != slow) {
  20.             if (fast.next == null || fast.next.next == null) {
  21.                 return false;
  22.             }
  23.             fast = fast.next.next;
  24.             slow = slow.next;
  25.         }
  26.         return true;
  27.     }
  28. }
复制代码
移除单链表倒数第N个元素

  解题思路:
  
       
  • 先从head循环n次,判断是否n大于链表长度,如果大于直接返回head   
  • 如果n正好是链表长度,那么返回head的next,相当于删除第一个元素   
  • 如果n是其他情况,那么从当前位置指针向后移动,直到结尾,用另外一个head指针同时向后移动   
  • 最后把当前head指针的next元素删除掉就好  
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public ListNode removeNthFromEnd(ListNode head, int n) {
  11.         ListNode begin = head;
  12.         ListNode end = head;
  13.         for (int i = 0; i < n; i++) {
  14.             if (end == null) {
  15.                 return head;
  16.             }
  17.             end = end.next;
  18.         }
  19.         if (end == null) {
  20.             return head.next;
  21.         }
  22.         while (end.next != null) {
  23.             begin = begin.next;
  24.             end = end.next;
  25.         }
  26.         begin.next = begin.next.next;
  27.         return head;
  28.     }
  29. }
复制代码
合并两个排序的单链表

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. * 递归算法求解
  9. */
  10. public class Solution {
  11.   public ListNode mergeTwoLists(ListNode l1, ListNode l2){
  12.       if (l1 == null) return l2;
  13.       if (l2 == null) return l1;
  14.       if (l1.val < l2.val) {
  15.           l1.next = mergeTwoLists(l1.next, l2);
  16.           return l1;
  17.       } else {
  18.           l2.next = mergeTwoLists(l1, l2.next);
  19.           return l2;
  20.       }
  21.   }
  22. }
复制代码
移除重复的元素从排序的链表当中

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public ListNode deleteDuplicates(ListNode head) {
  11.         ListNode current = head;
  12.         while (current != null) {
  13.             if (current.next != null && current.next.val == current.val) {
  14.                 current.next = current.next.next;
  15.             } else {
  16.                 current = current.next;
  17.             }
  18.         }
  19.         return head;
  20.     }
  21. }
复制代码
链表当中删除指定值的节点

  Example:
  Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
  Return: 1 –> 2 –> 3 –> 4 –> 5
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public ListNode removeElements(ListNode head, int val) {
  11.         ListNode dummy = new ListNode(0);
  12.         dummy.next = head;
  13.         head = dummy;
  14.         while (head.next != null) {
  15.             if (head.next.val == val) {
  16.                 head.next = head.next.next;
  17.             } else {
  18.                 head = head.next;
  19.             }
  20.         }
  21.         return dummy.next;
  22.     }
  23. }
复制代码
删除当前链表节点

  例如: 1 -> 2 -> 3 -> 4
  传入的节点是 3 ,那么指向完后列表是 1 -> 2 -> 4
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public void deleteNode(ListNode node) {
  11.         if (node.next == null) {
  12.             node = null;
  13.         }
  14.         node.val = node.next.val;
  15.         node.next = node.next.next;
  16.     }
  17. }
复制代码
交换链表节点的位置

  给定 1->2->3->4
  返回 2->1->4->3
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. public class Solution {
  10.     public ListNode swapPairs(ListNode head) {
  11.         ListNode dummy = new ListNode(0);
  12.         dummy.next = head;
  13.         head = dummy;
  14.         while (head.next != null && head.next.next != null) {
  15.             ListNode t1 = head.next;
  16.             ListNode t2 = head.next.next;
  17.             head.next = t2;
  18.             t1.next = t2.next;
  19.             t2.next = t1;
  20.             head = head.next.next;
  21.         }
  22.         return dummy.next;
  23.     }
  24. }
复制代码
—EOF—
友荐云推荐




上一篇:iOS原生二维码的生成与扫描
下一篇:Python3 图片隐写术
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

wojiaotom 发表于 2016-10-9 17:49:20
孩子把玩具当朋友,成人把朋友当玩具。
回复 支持 反对

使用道具 举报

李緣 发表于 2016-11-10 13:33:55
楼主你好。。新人。混眼熟。顺便骗点经验。到手~拍拍屁股走人~
回复 支持 反对

使用道具 举报

rdihj 发表于 2016-11-10 18:32:34
做好事不留名,都写在帖子里!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表