Java链表和递归

Java链表和递归

删除链表的指定元素：

public class ListNode { public int val; public ListNode next; public ListNode(int x){ val=x; } //链表节点的构造函数 //使用arr为参数，创建一个链表，当前的ListNode为链表头节点 public ListNode(int arr[]){ if(arr==null||arr.length==0) throw new IllegalArgumentException("arr can not be empty"); this.val=arr[0]; ListNode cur=this; for(int i=1;i"); cur=cur.next; } res.append("NULL"); return res.toString(); }}

第一种方法：

public class Solution { public ListNode removeElements(ListNode head,int val){ while(head!=null&& head.val==val){// ListNode delNode=head;// head=head.next;// delNode.next=null; head=head.next; } if(head==null) return null; ListNode prev=head; while(prev.next!=null){ if(prev.next.val==val){// ListNode delNode=prev.next;// prev.next=delNode.next;// delNode.next=null; prev.next=prev.next.next; } else{ prev=prev.next; } } return head; } public static void main(String[] args){ int[] nums={1,2,3,4,5,6}; ListNode head=new ListNode(nums); System.out.println(head); ListNode res=(new Solution()).removeElements(head, 6); System.out.println(res); }}

使用头节点：

public class Solution2 { public ListNode removeElements(ListNode head,int val){ ListNode dummyHead=new ListNode(-1); dummyHead.next=head; ListNode prev=dummyHead; while (prev.next!=null) { if(prev.next.val==val) prev.next=prev.next.next; else prev=prev.next; } return head; } public static void main(String[] args){ int[] nums={1,2,3,4,5,6}; ListNode head=new ListNode(nums); System.out.println(head); ListNode res=(new Solution2()).removeElements(head, 6); System.out.println(res); }}

实现求数组递归的算法：

public class Sum { public static int sum(int[] arr){ return sum(arr,0); } //计算arr[l...n]这个区间内所有数字的和 private static int sum(int[] arr,int l){ if(l==arr.length) return 0; return arr[l]+sum(arr,l+1); } public static void main(String[] args){ int[] nums={1,2,3,4,5,6,7,8}; System.out.println(sum(nums)); }}

用递归实现删除链表中的元素：

public class Solution3 { public ListNode removeElements(ListNode head,int val){ if(head==null) return null; head.next = removeElements(head.next, val); return head.val==val? head.next:head; } public static void main(String[] args){ int[] nums={1,2,3,4,5,6}; ListNode head=new ListNode(nums); System.out.println(head); ListNode res=(new Solution3 ()).removeElements(head, 6); System.out.println(res); }}　打印执行过程：

public class Solution3 {public ListNode removeElements(ListNode head,int val,int depth){String depthString=generateDepthString(depth);System.out.println(depthString);System.out.println("Call:remove "+val+"in "+head);if(head==null){System.out.print(depthString);System.out.println("Call:remove "+val+"in "+head);return null;}ListNode res=removeElements(head.next, val,depth+1);System.out.print(depthString);System.out.println("After remove "+val+":"+res);ListNode ret;if(head.val==val)ret=res;else{head.next=res;ret=head;}System.out.print(depthString);System.out.println("Return:"+ret);return ret;}private String generateDepthString(int depth){StringBuilder res=new StringBuilder();for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。