当前位置:首页 > 开发 > 互联网 > 正文

java-60-在O(1)时间删除链表结点

发表于: 2012-03-12   作者:bylijinnan   来源:转载   浏览:
摘要: public class DeleteNode_O1_Time { /** * Q 60 在O(1)时间删除链表结点 * 给定链表的头指针和一个结点指针(!!),在O(1)时间删除该结点 * * Assume the list is: * head->...->nodeToDelete->mNode->nNode->..

public class DeleteNode_O1_Time {

	/**
	 * Q 60 在O(1)时间删除链表结点
	 * 给定链表的头指针和一个结点指针(!!),在O(1)时间删除该结点
	 * 
	 * Assume the list is:
	 * head->...->nodeToDelete->mNode->nNode->...->tail
	 * you have already the point of 'nodeToDelete' in hand.So what you need to do is:
	 * 1.copy the data of 'mNode' to 'nodeToDelete'
	 * 2.nodeToDelete.next=nNode;
	 * However,when deleting the last node,you have to iterate from 'head'.No shortcut.
	 * 
	 * ---public static void deleteNode(Node head,Node nodeToDelete){
	 * cannot do it like that.Because you cannot set head=null to make 'list' empty.
	 * see 'class ParameterTransfer'
	 */
	public static void deleteNode(List list,Node nodeToDelete){
		Node head=list.head;
		if(head==null||nodeToDelete==null){
			return;
		}
		if(head.next==null&&nodeToDelete==head){//Only one node in list and you happen to delete the node.
			list.head=null;//head=null;-->wrong
			return;
		}
		Node node=head;
		if(node.next!=null&&nodeToDelete!=null){
			Node mNode=nodeToDelete.next;
			if(mNode!=null){
				Node nNode=mNode.next;
				nodeToDelete.data=mNode.data;
				nodeToDelete.next=nNode;
			}else {//'nodeToDelete' is the last Node.
				Node previous=node;
				while(node.next!=null){
					previous=node;
					node=node.next;
				}
				previous.next=null;
				return;
			}
			
		}
	}
	private static class List{
		private Node head;
		
		Node createList(int[] data){
			if(data==null||data.length==0){
				return null;
			}
			Node previous=null;
			for(int len=data.length,i=len-1;i>=0;i--){
				head=new Node(data[i]);
				head.next=previous;
				previous=head;
			}
			return head;
		}
		void printList(){
			Node node=head;//don't use 'head' immediately.It wastes my time to find the bug...
			while(node!=null){
				System.out.print(node.data+" ");
				node=node.next;
			}
			System.out.println();
		}
		Node getNodeAt(int pos){//starts from 0
			Node re=null;
			int index=0;
			Node node=head;
			while(node!=null){
				if(index==pos){
					return node;
				}
				node=node.next;
				index++;
			}
			return re;
		}
	}
	private static class Node{
		int data;
		Node next;
		Node(int data){
			this.data=data;
		}
	}
	
	public static void main(String[] args) {
		int[] data={0,1,2,3,4,5,6,7,8};
		List list=new List();
		list.createList(data);
		list.printList();
		
		Node nodeToDelete=list.getNodeAt(8);
		deleteNode(list,nodeToDelete);
		
		nodeToDelete=list.getNodeAt(3);
		deleteNode(list,nodeToDelete);
		
		nodeToDelete=list.getNodeAt(0);
		deleteNode(list,nodeToDelete);
		
		list.printList();//1 2 4 5 6 7
		
		list.createList(new int[]{1});
		deleteNode(list,list.getNodeAt(0));
		list.printList();//nothing.
		
	}
}




public class ParameterTransfer {

	/**
	 * 1.primitive type: pass by value
	 * 2.reference type: you can change the paremeter's status,but you cannot set it null.
	 */
	public static void main(String[] args) {
		ParameterTransfer p = new ParameterTransfer();
		TestData test = new TestData(1);
		p.setNull(test);
		System.out.println(test == null);// false--cannot set it null
		p.changeReference(test);
		System.out.println(test.i);//1--cannot change reference
		p.changeData(test);
		System.out.println(test.i);// 2--change its status
		
	}

	public void changeData(TestData test){
		test.i=2;
	}
	public void setNull(TestData test) {
		test = null;
		return;
	}
	
	public void changeReference(TestData test) {
		TestData test2=new TestData(2);
		test = test2;
		return;
	}
}

class TestData {
	int i;

	TestData(int i) {
		this.i = i;
	}
}

java-60-在O(1)时间删除链表结点

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点。 链表结点与函数的
方法一:顺序查找要删除的结点,并在链表中删除。时间复杂度为O(n),不满足题目要求 代码: void Del
代码实现: public class Test13 { /** * 链表结点 */ public static class ListNode { int value;
一、题目:在O(1)时间删除链表结点 题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)
在O(1)时间删除链表的节点 题目: 给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除
题目: 给你一个单链表的表头,再给你其中某个结点的指针,要你删除这个结点,条件是你的程序必须在
今天做了一道传说中的Google面试题,好吧,题目大致是这样的。 有如下的一个单链表结点定义 1 //链
下图是一个创建好的链表 下面我们需要删除一个结点,例如删除第3个结点 首先定义一个指针p,并且将p
算法的思想就是:把P的前驱结点接上P的后继节点。然后P的后继节点的前驱节点指向P的前驱节点。这个
问题及代码: /* *Copyright (c)2014,烟台大学计算机与控制工程学院 *All rights reserved. *文件名
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号