剑指Offer面试题12打印1到最大的n位数，面试题13在O(1)时间删除链表结点

面试题12：打印1到最大的n位数

输入数字n,按顺序打印出从1最大的n位十进制数。例如输入3，则打印出1,2,3,...,一直到最大的3位数即999。

注意：没有限定n的范围时，注意大数问题，n可能会超出基本数值类型的表示范围，此时可以用字符串来表示，每一位上都是0-9的遍历，可以用递归。

题外话：java中有两个类BigInteger和BigDecimal分别表示大整数类和大浮点数类，理论上能表示无限大的数。

本题利用字符串和递归方法的Java实现：

public class PRint1ToMaxOfNDigits {	private void print(String str,int len){        if (len == 0) {//递归结束条件        	for(int j = 0;j < str.length();j++){//不输出字符串前边的0        		if(str.charAt(j) != '0'){        			System.out.println(str.substring(j));        			break;        		}        	}            return;        }        for (int i = 0; i < 10; i++) {            print(str + i,len - 1);            //递归说明：程序先第一次进入循环体，进入第一层递归输入是(0,1)，不满足递归结束条件，然后第二次进入循环体，再进入第二层递归输入是(00,0),满足结束条件输出00，            //然后回到第二次进入的循环体中，执行循环体的第二轮，会进入新的第二层递归输入是(01,0),满足结束条件输出01，以此类推，直到09，这个循环体结束，            //此时第一层递归结束，程序开始执行第一次进入的循环体的第二轮，会进入新的第一层递归，输入是(1,1),以此类推。        }    }    private void print1ToMaxOfDigits(int n) {    	if(n <= 0){    		System.out.println("输入有误");    		return;    	}        print("", n);    }    public static void main(String[] args) {        Print1ToMaxOfNDigits test=new Print1ToMaxOfNDigits();        test.print1ToMaxOfDigits(2);    }}
面试题13：在O(1)时间删除链表结点
给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
思路：一般思路是从头开始遍历，这样复杂度是O(n)不合题意。我们的方法是把该节点的值设为该节点下一个节点的值，然后让该节点指向下下一个节点。
这样会有三种情况：1，要删除的节点不是尾节点。2，链表只有一个节点3，要删除的节点是尾节点，只能从头到尾遍历了。最后平均一下复杂度还是O(1)。
本题的Java实现：
class ListNode{	int value;	ListNode next;	ListNode(int x){		value = x;		next = null;	}}public class DeleteNode {	static void delete(ListNode headNode,ListNode toBeDeleted){		if(headNode == null || toBeDeleted == null){			System.out.println("都是null");			return;		}		if(toBeDeleted.next != null){//1,要删除的节点不是尾节点			toBeDeleted.value = toBeDeleted.next.value;			toBeDeleted.next = toBeDeleted.next.next;		}else if(headNode.next == toBeDeleted){//2，链表只有一个节点，要把头指针设为NULL。			headNode.next = null;		}else{//3，要删除的节点是尾节点			while(headNode.next != toBeDeleted){				headNode = headNode.next;			}			headNode.next = null;		}	}	public static void main(String[] args){		ListNode head = new ListNode(0);		ListNode one = new ListNode(1);		ListNode two = new ListNode(2);		head.next = one;		one.next = two;		delete(head, one);		while(head != null){			System.out.println(head.value);			head = head.next;		}	}}
本题的C语言实现：
void delete_node(plist &headnode,plist pdele){ //参数是头结点和要删除的节点	if(headnode == NULL || pdele == NULL) return;	//要删除的节点不是尾节点	if(pdele->next != NULL){		plist pnext = pdele->next;		pdele->data = pnext->data;		pdele->next = pnext->next;		free(pnext);	}else if(pdele == headnode){//链表只有一个节点，删除头结点（也是尾节点）		free(pdele);		headnode = NULL;	}else{//链表中有多个节点，删除尾节点		plist pnode = headnode;		while(pnode->next != pdele){			pnode = pnode->next;		}		pnode->next = NULL;		free(pdele);	}}调用：delete_node(head,delenode);
注意：有关指针传参可参看剑指Offer面试题5反向打印链表的c实现。