鏈表反轉(zhuǎn)
方法一：迭代法
保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)合砂，防止掉鏈;當(dāng)前節(jié)點(diǎn)的next指針指向前一個(gè)節(jié)點(diǎn)；
向后移動(dòng)節(jié)點(diǎn)珍策。
public ListNode ReverseList(ListNode head) {
ListNode prev=null;
while(head!=null){
ListNode temp=head.next;
head.next=prev;
prev=head;
head=temp;
}
return prev;
}
方法二：遞歸法
合并有序鏈表
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy=new ListNode(0);
ListNode p=dummy,p1=list1,p2=list2;
while(p1!=null&&p2!=null){
if(p1.val<=p2.val){
p.next=p1;
p1=p1.next;
}else{
p.next=p2;
p2=p2.next;
}
p=p.next;
}
if(p1!=null)
p.next=p1;
if(p2!=null)
p.next=p2;
return dummy.next;
}
找到倒數(shù)第k個(gè)節(jié)點(diǎn)
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k==0)
return null;
ListNode node=head;
for(int i=0; i<k;i++){
if(node==null)
return null;
node=node.next;
}
while(node!=null){
head=head.next;
node=node.next;
}
return head;
}
