Skip to content

Commit

Permalink
linkedlist notes update
Browse files Browse the repository at this point in the history
rwang23 committed Nov 13, 2015
1 parent 75e96a5 commit 2b68de2
Showing 6 changed files with 63 additions and 34 deletions.
8 changes: 3 additions & 5 deletions Linkedlist/Linked-List-Cycle.md
Original file line number Diff line number Diff line change
@@ -3,7 +3,6 @@
47% Accepted

Given a linked list, determine if it has a cycle in it.
Have you met this question in a real interview? Yes
Example
Given -21->10->4->5, tail connects to node index 1, return true

@@ -41,18 +40,17 @@ public class Solution {
}
ListNode fast = head;
ListNode slow = head;
boolean isCycle = false;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
isCycle = true;
break;
return true;
}
}
return isCycle;
return false;
}
}



```
50 changes: 48 additions & 2 deletions Linkedlist/Remove-Duplicates-from-Sorted-ListII.md
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
##Remove Duplicates from Sorted List II Show result
##Remove Duplicates from Sorted List II

27% Accepted

@@ -21,8 +21,9 @@ Linked List
```java
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
if(head == null || head.next == null) {
return head;
}

ListNode dummy = new ListNode(0);
dummy.next = head;
@@ -43,3 +44,48 @@ public class Solution {
}
}
```

####原来的看不明白了 又写了一下
- 关键还是在于preNode

```java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode preNode = dummy;

int tempValue = head.val;
while (head != null) {
ListNode nextNode = head.next;
boolean isDuplicates = false;
while (nextNode != null && tempValue == nextNode.val) {
nextNode = nextNode.next;
isDuplicates = true;
}
if (isDuplicates) {
preNode.next = nextNode;
} else {
preNode = preNode.next;
}
if (nextNode != null) {
tempValue = nextNode.val;
}
head = nextNode;

}
return dummy.next;
}
}
```
10 changes: 10 additions & 0 deletions Linkedlist/Remove-Duplicates-from-Unsorted-List.md
Original file line number Diff line number Diff line change
@@ -57,3 +57,13 @@ public class Solution {
}

```

####O(1) space思路
1. This is the simple way where two loops are used. Outer loop is used to pick the elements one by one and inner loop compares the picked element with rest of the elements.
2. In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. We will soon be writing a post about sorting a linked list. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)

Please note that this method doesn’t preserve the original order of elements.

Time Complexity: O(nLogn)
4 changes: 0 additions & 4 deletions Linkedlist/Reorder-List.md
Original file line number Diff line number Diff line change
@@ -7,10 +7,6 @@

You must do this in-place without altering the nodes' values.



Have you met this question in a real interview? Yes
Example
For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

23 changes: 1 addition & 22 deletions Linkedlist/Rotate-List.md
Original file line number Diff line number Diff line change
@@ -17,28 +17,7 @@


```java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/

public class Solution {
/**
* @param head: the List
2 changes: 1 addition & 1 deletion SUMMARY.md
Original file line number Diff line number Diff line change
@@ -115,7 +115,7 @@ This is the summary of my experience in LintCode.
* [Remove Duplicates From Sorted List](Linkedlist/Remove-Duplicates-from-Sorted-ListII.md)
* [Linked List Cycle](Linkedlist/Linked-List-Cycle.md)
* [Linked List Cycle II](Linkedlist/Linked-List-CycleII.md)
* [Swap Nodels in Pairs](Linkedlist/Swap-Nodes-in-Pairs.md)
* [Swap Nodes in Pairs](Linkedlist/Swap-Nodes-in-Pairs.md)
* [Intersection of Two Linked Lists](Linkedlist/Intersection-of-Two-Linked-Lists.md)
* [Merge Two Sorted Lists](Linkedlist/Merge-Two-Sorted-Lists.md)
* [Merge K Sorted Lists](Linkedlist/Merge-k-Sorted-Lists.md)

0 comments on commit 2b68de2

Please sign in to comment.