在0(1)时间内删除链表节点
每一个节点只有后继没有前驱
分析:
要考虑三种状况,链表只有一个元素、要找的这个节点的next为空他在链表尾部或者没有,要找的节点在中间node
尾部的话用笨办法去找
若是在中间,把他的下一个节点的值给他,而后删除下一个节点就行
若是是就一个元素,删除头部返回为空。web
public static class Node{ Node next; int val; public Node(int val,Node pnext){ this.val = val; this.next = pnext; } public Node(){} } public static Node deleteNode(Node head,Node pnode){ if(head == null||pnode == null){ return null; }//代码鲁棒 if(head == pnode){ pnode = null; head = null; return head; } else if(pnode.next!=null){//要删的节点是中间节点 pnode.val = pnode.next.val;//把要删的节点的值给他的下一个节点 pnode.next = pnode.next.next;//删掉他的下一个节点 }else{//若是这节点在最后,由于你不知道他的下一个节点是什么又没有他的前驱来肯定他的位置,只能在 //从头至尾开始找直到最后,找到删掉或者没有这个节点 Node tempNode = head ; while(tempNode.next!=pnode && tempNode!=null){ tempNode = tempNode.next; } if(tempNode==null){ System.out.println("No this Node"); return head; } tempNode.next = null; pnode = null; } return head; } public static void travelist(Node head){ Node curr = head; while(curr!=null){ System.out.print(curr.val+" "); curr = curr.next; } System.out.println(); }
public static void main(String[] args) { Node p5 = new Node (5,null); Node p4 = new Node (4,p5); Node p3 = new Node (3,p4); Node p2 = new Node (2,p3); Node p1 = new Node(1,p2); Node result = deleteNode(p5,p5); Node result1 = deleteNode(p1,p2); Node result2 = deleteNode(p1,p3); Node result3 = deleteNode(p1,p4); Node result4 = deleteNode(p1,p5); travelist(result); }
操蛋?????svg