java程序员面试金典 2

1. 输入一个链表，输出该链表中倒数第k个结点。

public class ListNode{
     int val;
     ListNode next=null;
     ListNode(int val){
          this.val=val;
     }
}


public class Solution{
    public ListNode findKthToTail(ListNode head,int k){
        if(head==null || k<=0)  //判断传入头节点和K值是否符合要求
            return null;
       ListNode curNode=head;   //定义两个节点
        ListNode preNode=head;
        for(int i=1;i<k;i++){      //前面那个节点移动k-1步   需要注意：判断下一节点是否为空
           if(curNode.next!=null){   
              curNode=curNode.next;
           }else{    
              return null; 
           }
        }
        while(curNode .next!=null){  //当前面节点下一节点不为空时 两个节点继续右移 直到前面节点为空
           curNode=curNode.next;
           preNode=preNode.next;
        }
        return preNode;  //
       }
  }

2 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

//分割链表  新增大小两个链表  最后合起来即可
public ListNode partition(ListNode pHead,int x){
   if(pHead ==null || pHead.next==null){   //若头节点为空或者只有一个节点时返回该节点
          return pHead;
   }

    ListNode curNode=pHead;  //当前节点
    ListNode   smallNode=new ListNode(-1);  //新建小链表的头节点
    ListNode   bigNode=new ListNode(-1);    //新建大链表的头节点
    ListNode   sNode=smallNode;       //记录小链表头节点的位置   便于后期返回头节点
    ListNode   bNode=bigNode;   //记录大链表的头节点位置   便于后期合并


    while( curNode!=null){   //当前节点不为空时
         if(curNode.val>=x){    //判断当前节点值与给定值的大小  从而分配链表
               bigNode.next=curNode;    //大值分配给bigNode  并向后移动
               bigNode=bigNode.next;
          }else{
                smallNode.next=curNode;  //小值分配给smallNode  并向右移动
                smallNode=smallNode.next;
           } 
           curNode=curNode.next;   // 分配完毕  继续移动到下一节点  重复分配动作
      }

     // 分配完毕  开始连接两个链表
    smallNode.next=bNode.next;  //小链表的尾节点的下一节点  连接到  大链表的头节点
    bigNode.next=null;  // 大 链表的尾节点 下一节点为null值

    return sNode.next;  //返回小 链表的头节点
} 

另外的一种思路： 用ArrayList把数据提取出来   然后再创建链表 把数据存进去

public static ListNode pertition(ListNode pHead,int x){
   ArrayList<Integer> less=new ArrayList<Integer>();
   ArrayList<Integer> eq=new ArrayList<Integer> ();
   ArrayList<Integer>  more=new ArrayList<Integer>();

   while(pHead!=null){
     if(pHead.val==x){
         eq.add(pHead.val);
     }else if( pHead.val>x){
         more.add(pHead.val);
     }else{
         less.add(pHead.val);
     }
    pHead=pHead.next;
   }

    less.addAll(more); //将more追加到less末尾
    less.addAll(eq);
    //现在所有数据均按照从小到大的顺序存在less集合中
    //重新创建链表  一个个节点开始创建
    pHead=null;
    ListNode p=null;
    for(Integer a:less){
       if(pHead==null){
           p=pHead=new ListNode(a);
       }else{
           p.next=new ListNode(a);
           p=p.next;
       }
     }
    return pHead;
}