Linked List Cycle
Linked List Cycle II
http://www.cnblogs.com/hiddenfox/p/3408931.html
http://www.cnblogs.com/wuyuegb2312/p/3183214.html
Leetcode: Linked List Cycle & Linked List Cycle II
Reply
Category Archives: List
Leetcode: Pascal’s Triangle
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> pascalTriangle = new ArrayList<List<Integer>>();
List<Integer> currLevel = new ArrayList<Integer>();
currLevel.add(1);
while(numRows>0){
pascalTriangle.add(new ArrayList<Integer>(currLevel));
currLevel = generateNextLevel(currLevel);
numRows--;
}
return pascalTriangle;
}
public List<Integer> generateNextLevel(List<Integer> currLevel){
List<Integer> nextLevel = new ArrayList<Integer>();
if(currLevel.size()!=0){
currLevel.add(0);
currLevel.add(0,0);
for(int runner=0; runner<currLevel.size()-1; runner++){
nextLevel.add(currLevel.get(runner)+currLevel.get(runner+1));
}
}
return nextLevel;
}
}
Note: for each row, pretend there is always one 0 at each side of the row. So the triangle would look like following, so when calculating next level, just need to sum each adjacent integers in the current level.
[
0[1]0,
0[1,1]0,
0[1,2,1]0,
0[1,3,3,1]0,
0[1,4,6,4,1]0
]
Leetcode: Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
//non-recursive version
public ListNode swapPairs(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if(head==null||head.next==null){
return head;
}
ListNode runner = head;
ListNode newHead = null;
ListNode tail = null;
while(runner!=null && runner.next!=null){
ListNode runnernext = runner.next;
ListNode runnernextnext = runnernext.next;
if(tail!=null){
tail.next = runnernext;
}else{
newHead=runnernext;
}
runnernext.next = runner;
runner.next = null;
tail=runner;
runner = runnernextnext;
}
if(runner!=null){
tail.next = runner;
}
return newHead;
}
//recursive version
public ListNode swapPairs(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if(head==null||head.next==null){
return head;
}
ListNode headnext =head.next;
ListNode headnextnext=headnext.next;
head.next = swapPairs(headnextnext);
headnext.next=head;
return headnext;
}
Leetcode: Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public ListNode mergeKLists(ArrayList<ListNode> lists) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode fakeHead = new ListNode(-1);
ListNode runner = fakeHead;
int nonTraversed = 0;
//count the number of not-null ListNode
for(ListNode curr:lists){
if(curr!=null){
nonTraversed++;
}
}
while(nonTraversed>0){
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int i=0;i<lists.size();i++){
ListNode curr = lists.get(i);
if(curr!=null){
if(curr.val<min){
minIndex = i;
min = curr.val;
}
}
}
runner.next = lists.get(minIndex);
runner = runner.next;
lists.set(minIndex, lists.get(minIndex).next);
if(lists.get(minIndex)==null){
nonTraversed--;
}
}
return fakeHead.next;
}
O(N*k) k is the size of lists and N is the total number of elements in all the inputs lists
We can improve our solution by using Heap which can have O(Nlogk) runtime complexity.
Leetcode: Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode runner1=l1;
ListNode runner2=l2;
ListNode head = new ListNode(-1);
ListNode runner = head;
int carry=0;
while(runner1!=null || runner2!=null ||carry!=0){
int val1 = runner1==null?0:runner1.val;
int val2 = runner2==null?0:runner2.val;
int sum =val1+val2+carry;
if(sum>9){
carry=1;
}else{
carry=0;
}
runner.next = new ListNode(sum%10);
runner = runner.next;
runner1 = runner1==null?null:runner1.next;
runner2 = runner2==null?null:runner2.next;
}
return head.next;
}
Leetcode: Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Start typing your Java solution below
// DO NOT write main() function
//a fake head
//we should return head.next at the end
ListNode head = new ListNode(0);
ListNode newRunner = head;
ListNode runner1 = l1;
ListNode runner2 = l2;
while(runner1!=null && runner2!=null){
if(runner1.val<=runner2.val){
newRunner.next = runner1;
runner1 = runner1.next;
}else{
newRunner.next = runner2;
runner2 = runner2.next;
}
newRunner = newRunner.next;
}
newRunner.next = runner1==null?runner2:runner1;
return head.next;
}
Leetcode: Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
public class Solution {
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root==null){
return;
}
if(root.left==null){
flatten(root.right);
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
if(right!=null){
//find the right most element in root's left subtree
//add root's right subtree to the element as a right child
TreeNode runner = left;
while(runner.right!=null){
runner = runner.right;
}
runner.right = right;
}
root.right=left;
flatten(left);
}
Leetcode: Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode head = new ListNode(-1);
ListNode runner = head;
int carry = 0;
while(l1!=null || l2!=null){
int val1 = l1==null?0:l1.val;
int val2 = l2==null?0:l2.val;
int sum = val1 + val2 + carry;
if(sum>9){
sum = sum - 10;
carry = 1;
}else{
carry = 0;
}
if(head.val==-1){
head.val = sum;
}else{
ListNode newNode = new ListNode(sum);
runner.next = newNode;
runner = runner.next;
}
l1 = l1==null?null:l1.next;
l2 = l2==null?null:l2.next;
}
if(carry==1){
ListNode newNode = new ListNode(1);
runner.next = newNode;
}
return head;
}
}