Linked List Cycle

Linked List Cycle II

http://www.cnblogs.com/hiddenfox/p/3408931.html

http://www.cnblogs.com/wuyuegb2312/p/3183214.html

Reply

Linked List Cycle

Linked List Cycle II

http://www.cnblogs.com/hiddenfox/p/3408931.html

http://www.cnblogs.com/wuyuegb2312/p/3183214.html

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 ]

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; }

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.

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; }

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; }

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); }

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; } }