【算法】设计链表707

设计链表707 from leetcode

单链表

//设计链表707
public class DesignLinkedList707 {
	public static void main(String[] args){
	//单链表
	MyLinkedList myLinkedList = new MyLinkedList();

	myLinkedList.addAtHead(1);
	myLinkedList.printLinkedList();				// 1 -> 

	myLinkedList.addAtTail(3);
	myLinkedList.printLinkedList();				// 1 -> 3

	myLinkedList.addAtIndex(1, 2);      
	myLinkedList.printLinkedList();				// 1->2->3

	System.out.println(myLinkedList.get(1));    // 返回 2

	myLinkedList.deleteAtIndex(1);    
	myLinkedList.printLinkedList(); 			// 现在，链表变为 1->3

	System.out.println(myLinkedList.get(1));    // 返回 3

}


//单链表
class ListNode {
	int val;

	ListNode next;

	public ListNode(){

	}

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

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

}
class MyLinkedList {
	//虚拟节点
	ListNode dummy;

	int size;


    public MyLinkedList() {
    	size = 0;
    	dummy = new ListNode(-1);
    }
    /**
     * 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
     */
    public int get(int index) {
    	if (index < 0 || index >= size) {
    		//越界了
    		return -1;
    	}
    	ListNode cur = dummy.next;//0
    	for(int i = 0;i < index; i++){
    		cur = cur.next;
    	}
    	return cur.val;
    }
    /**
     * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     */
    public void addAtHead(int val) {
    	addAtIndex(0,val);
    }
    /**
     * 将值为 val 的节点追加到链表的最后一个元素。
     */
    public void addAtTail(int val) {
    	addAtIndex(size,val);
    }
    /**
     * 在链表中的第 index 个节点之前添加值为 val  的节点。
     * 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index 大于链表长度，则不会插入节点。
     * 如果index小于0，则在头部插入节点。
     * 
     */ 
    public void addAtIndex(int index, int val) {
 		
 		if (index < 0) {
 			index = 0;
 		}
 		if (index > size) {
 			return;
 		}

 		//中间正常插入

 		
 		ListNode addListNode = new ListNode(val);
 		//找到前继节点
 		ListNode pre = dummy;
 		for (int i = 0;  i < index; i++) {
 			pre = pre.next;
 		}

 		addListNode.next = pre.next;
 		pre.next = addListNode;
 		size++;
    }
    /**
     * 如果索引 index 有效，则删除链表中的第 index 个节点。
     */ 
    public void deleteAtIndex(int index) {
    	//安全性检验
    	if (index < 0 || index >= size) {
    		return;
    	}
    	//找到 deleteIndexListNode 前面一个 ListNode
    	ListNode pre = dummy;
    	for (int i = 0; i < index; i++) {
    		pre = pre.next;
    	}

    	pre.next = pre.next.next;
    	size--;

    }

    public void printLinkedList(){
    	if (size == 0) {
    		return;
    	}
    	ListNode cur = dummy.next;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }
}

双向链表

//设计链表707
public class DesignLinkedList707 {
	public static void main(String[] args){
	
	MyLinkedList myLinkedList = new MyLinkedList();

	myLinkedList.addAtHead(1);
	myLinkedList.printLinkedList();				// 1 -> 

	myLinkedList.addAtTail(3);
	myLinkedList.printLinkedList();				// 1 -> 3

	myLinkedList.addAtIndex(1, 2);      
	myLinkedList.printLinkedList();				// 1->2->3

	System.out.println(myLinkedList.get(1));    // 返回 2

	myLinkedList.deleteAtIndex(1);    
	myLinkedList.printLinkedList(); 			// 现在，链表变为 1->3

	System.out.println(myLinkedList.get(1));    // 返回 3

	}
}

//双链表
class ListNode {
	ListNode prev,next;
	int val;

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


class MyLinkedList {
	int size;
	ListNode head,tail;

	public MyLinkedList(){
		size = 0;
		head = new ListNode(-1);
		tail = new ListNode(-1);
		head.next = tail;
		tail.prev = head;
	}
	public int get(int index){
		
		if (index < 0 || index >= size){
			return -1;
		}
		//判断从那边开始找
		ListNode cur = head;
		if (index > size/2) {
			//从后面开始找
			cur = tail;
			for(int i = 0; i < size - index; i++){
				cur = cur.prev;
			}
		} else {
			//从前面开始找
			for(int i = 0; i <= index; i++){
				cur = cur.next;
			}
		}
		return cur.val;
	}

	public void addAtHead(int val) {
		addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
    	addAtIndex(size,val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
    	
    	if (index > size) {
    		return;
    	}
    	if (index < 0) {
    		index = 0;
    	}
    	ListNode frontNode = head;
    	for(int i = 0; i < index; i++){
    		frontNode = frontNode.next;
    	}
    	//现在 frontNode 就是要插入节点位置前一个
    	ListNode insertNode = new ListNode(val);
    	insertNode.next = frontNode.next;
    	frontNode.next.prev = insertNode;
    	insertNode.prev = frontNode;
    	frontNode.next = insertNode;

    	size++;
    }
    
    public void deleteAtIndex(int index) {
    	if (index < 0 || index >= size) {
    		return;
    	}
    	ListNode frontNode = head;
    	for (int i = 0; i < index; i++) {
    		frontNode = frontNode.next;
    	}
    	//现在 frontNode 就是要删除节点的上一个节点
    	frontNode.next.next.prev = frontNode;
    	frontNode.next = frontNode.next.next;
    	size--;
    }

    public void printLinkedList(){
    	ListNode cur = head.next;
    	while(cur != tail){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }
}