Chinaunix首页 | 论坛 | 博客
  • 博客访问: 112133
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2015-02-13 16:31:52

-- O(1)删除链表节点
    >> 题目:如何在O(1)时间复杂度和空间的条件下,删除某个节点。
    >> 解题思路:如果直接删除该节点,需要O(n)的时间复杂度来寻找前一个节点,显然不能达到要求;那么就不能采用该方法,寻找后继节点,将后继节点中的内容拷贝到该节点,然后删除后继节点。这样只有在删除最后节点的时候,需要遍历链表寻找其前一个节点。

-- Swap Nodes in Pair
    >> 题目:将链表中相邻另个节点交换顺序。    
    >> 解题思路:两两一组交换node的内容。

-- Sort List ?
    >> 题目:对链表进行排序,要求时间复杂度为O(n * logn),空间为常数
    >> 解题思路:归并排序。

点击(此处)折叠或打开

  1.     public ListNode sortList(ListNode head) {

  2.         return mergeSort(head);
  3.     }

  4.     private ListNode mergeSort(ListNode head) {
  5.         if (head == null || head.next == null)
  6.             return head;
  7.         ListNode slow = head, fast = head;
  8.         // when head is a 2 ele data, this is ok;
  9.         while (fast.next != null && fast.next.next != null) {
  10.             slow = slow.next;
  11.             fast = fast.next.next;
  12.         }
  13.         fast = slow.next;
  14.         slow.next = null;
  15.         slow = mergeSort(head);
  16.         fast = mergeSort(fast);
  17.         return merge(slow, fast);
  18.     }

  19.     private ListNode merge(ListNode head1, ListNode head2) {
  20.         ListNode helper = new ListNode(0);
  21.         helper.next = head1;
  22.         ListNode pre = helper;
  23.         while (head1 != null && head2 != null) {
  24.             if (head1.val < head2.val) {
  25.                 head1 = head1.next;
  26.             } else {
  27.                 ListNode next = head2.next;
  28.                 head2.next = pre.next;
  29.                 pre.next = head2;
  30.                 head2 = next;
  31.             }
  32.             pre = pre.next;
  33.         }
  34.         if (head2 != null) {
  35.             pre.next = head2;
  36.         }
  37.         return helper.next;
  38.     }

-- Rotate List
    >> 题目:将给定链表中的后k个数,移到链表前面
    >> 解题思路:主要处理溢出问题,首先得到链表的长度,求余,对于0的直接返回,其余的移动

点击(此处)折叠或打开

  1.     public ListNode rotateRight(ListNode head, int n) {
  2.         if (head == null || n == 0) return head;
  3.         ListNode slow = head, fast = head, temp = null;
  4.         int count = 1;
  5.         
  6.         while (fast != null) {
  7.             fast = fast.next;
  8.             count++;
  9.         }
  10.         n = n % count;
  11.         if (n == 0) return head;
  12.         fast = head;
  13.         
  14.         int i = 0;
  15.         for (i = 0; i < n && fast != null; i++) {
  16.             fast = fast.next;
  17.         }
  18.         if (fast == null) {
  19.             return head;
  20.         }
  21.         while (fast.next != null) {
  22.             slow = slow.next;
  23.             fast = fast.next;
  24.         }
  25.         temp = slow.next;
  26.         slow.next = null;
  27.         fast.next = head;
  28.         return temp;
  29.     }

-- Reverse Nodes in k-Group
    >> 题目:将链表的每k个为一组进行逆序
    >> 解题思路:比较简单的是值交换。使用栈。

-- Reverse Listed List II
    >> 题目:将链表中的某一段进行逆序
    >> 解题思路:目前的实现也是值交换,使用栈。

-- Remove Nth Node From End of List
    >> 题目:删除链表中倒数第n个node
    >> 解题思路:遍历,将其转换成正向的,然后删除。

-- Remove Duplicates from Sorted List II
    >> 题目:从排序链表中删除重复的。
    >> 解题思路:遍历, 注意特殊情况。

-- Partition List
    >> 题目:调整链表的顺序,使链表中比x小的节点全部都放在前面,但是得保持其在原始链表中的顺序。
    >> 解题思路:遍历,注意使用简单删除中的顺序问题。

-- Merge Two Sorted Lists
    >> 题目:将两个排好序的链表合并
    >> 解题思路:合并,但是越简单越好,也就是使用额外的首节点。

-- Merge K Sorted Lists
    >> 题目:将k个list排序
    >> 解题思路:合并,调用Merge Two Sorted Lists

-- Linked List Cycle
    >> 题目:判断链表中是否有环
    >> 解题思路:两个指针遍历,速度不同。
    
-- Linked List Cycle II
    >> 题目:判断链表中是否有环,并返回环的起点。
    >> 解题思路:注意如果一开始就入环,处理方法不太一样,所有的需要加个前缀节点,使两种情况归一化。

-- Intersection of Two Linked Lists 
    >> 题目:输出两个链表的交叉区域
    >> 解题思路:先遍历,统计两个链表的数量,并判断是否有交叉,然后根据交叉数计算开始位置。遍历,找到真正的起始位置

-- Insertion Sort List
    >> 题目:插入排序链表

-- Copy List with Random Pointer 
    >> 题目:copy链表,但是这个链表,有两个指针,一个指向后继节点,另一个指向随机节点
    >> 解题思路:遍历,生成map,再遍历,设置指针

-- sorted List to BST
    >> 题目:从排序链表,生成BST
    >> 解题思路:递归,每个可以从头查找,这个不是最大的限制因素。









阅读(414) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册