Linklist
定义：node includes pointer(next) and value
区别（与Array）:Array has indice,which is in sequence,LinkList has pointer to next.
single list and double list.
package Linkedlist;
public class ListNode {
ListNode next=null;
int val;
public ListNode(int d){
this.val=d;
}
public void appenttotail(int d){
ListNode end=new ListNode(d);
ListNode n=this;
while(n.next!=null){
n=n.next;
}
n.next=end;
}
public ListNode DelectNode(ListNode head,int d){
ListNode n=head;
if(n.next==null){
return head.next;
}else{
while(n.next!=null){
if(n.val==d){
n.next=n.next.next;
return head;
}
n=n.next;
}
return head;
}
}
}
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
package Linkedlist; public class ADD2NUM { public ListNode addTwoNumbers(ListNode head1, ListNode head2) { if(head1==null){ return head2; } if(head2==null){ return head1; } int carry=0; ListNode newhead=new ListNode(-1); ListNode res=newhead; while(head1!=null||head2!=null){ if(head1!=null) { carry=carry+head1.val; head1=head1.next; } if(head2!=null) { carry=carry+head2.val; head2=head2.next; } res.next=new ListNode((carry)%10); carry=carry/10; res=res.next; } if(carry==1) { res.next =new ListNode(1); } return newhead.next; } }
19.Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
暴力版
public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode res=head; ListNode fina=res; if(head==null||(head.next==null&&n==1)){ return null; } if(n==0){ return head; } int count=0; if(n==1){ while(head.next.next!=null){ head=head.next; } head.next=null; return fina; } if(n!=1){ while(head!=null){ head=head.next; count++; } } if(n==count){ return fina.next; } int j=1; while(res.next!=null){ if(j==(count-n)){ res.next=res.next.next; return fina; } res=res.next; j++; } return fina; } }
双指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode res=head; ListNode fal=head; if(head==null||(head.next==null&&n==1)){ return null; } if(n==0){ return head; } for(int i=0;i<n;i++){ res=res.next; } if(res==null){ return head.next; } while(res.next!=null){ res=res.next; fal=fal.next; } fal.next=fal.next.next; return head; } }
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.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode newhead=new ListNode(0); ListNode l3=newhead; if(l1==null){ return l2; } if(l2==null){ return l1; } while(l1!=null&&l2!=null){ if(l1.val<l2.val){ l3.next=new ListNode(l1.val); l1=l1.next; }else{ l3.next=new ListNode(l2.val); l2=l2.next; } l3=l3.next; } if(l1==null&&l2!=null){ l3.next=l2; } if(l2==null&&l1!=null){ l3.next=l1; } return newhead.next; } }
原文：http://www.cnblogs.com/joannacode/p/4555995.html