1.合并两个排好序的list
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
2.删除list倒数第n个元素
Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
两个问题合在一个工程里面测试
1 package com.rust.datastruct; 2 3 public class MergeTwoSortedLists { 4 public static ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) { 5 ListNode r1 = new ListNode(0); 6 ListNode res = r1; 7 ListNode t1 = l1;//java 中这样的赋值操作，对了l1操作等同于对t1操作 8 ListNode t2 = l2; 9 while (t1 != null && t2 != null){ 10 if (t1.val <= t2.val) { 11 r1.next = t1; 12 t1 = t1.next; 13 } else { 14 r1.next = t2; 15 t2 = t2.next; 16 } 17 r1 = r1.next; 18 } 19 if (t1 != null) { 20 r1.next = t1; 21 } 22 if (t2 != null) { 23 r1.next = t2; 24 } 25 res = res.next; 26 return res; 27 } 28 /** 29 * @param head 30 * @param n 31 * @return ListNode 32 */ 33 public static ListNode removeNthFromEnd(ListNode head, int n) { 34 if (n == 0) return head; 35 ListNode fakeNode = head; 36 int count = 0; 37 while (fakeNode != null) { 38 fakeNode = fakeNode.next; 39 count++; 40 } 41 fakeNode = head; 42 if (n == count) { 43 head = head.next; 44 return head; 45 } else { 46 for (int i = 0; i < count; i++) { 47 if (i + n + 1== count) { 48 System.out.println(fakeNode.val); 49 ListNode cut = fakeNode.next.next; 50 fakeNode.next = cut; 51 count--; 52 continue; 53 } 54 fakeNode = fakeNode.next; 55 } 56 } 57 return head; 58 } 59 60 public static void main(String args[]){ 61 ListNode l1 = new ListNode(0); 62 ListNode l2 = new ListNode(1); 63 ListNode p1 = l1; 64 ListNode p2 = l2; 65 /*initial the list*/ 66 for (int i = 2; i <= 10; i++) { 67 if (i%2 == 0) { 68 p1.next = new ListNode(i); 69 p1 = p1.next; 70 } else { 71 p2.next = new ListNode(i); 72 p2 = p2.next; 73 } 74 } 75 p1 = l1; 76 p2 = l2; 77 System.out.println("input List l1 and l2"); 78 showData(l1, l2);//after show,l1 and l2 value didn't change! 79 System.out.println("mergeTwoLists(l1, l2) -->"); 80 ListNode res = mergeTwoSortedLists(l1, l2); 81 /** test mergeTwoSortedLists start ************/ 82 while (res.next != null) {// res is destroyed 83 System.out.print(res.val + "\t"); 84 res = res.next; 85 } 86 System.out.println(res.val); 87 System.out.println("After merge"); 88 /** End ***********************************/ 89 /** test removeNthFromEnd start **************/ 90 showData(l1, l2); 91 // use l2 to test 92 int n = 1; 93 l2 = removeNthFromEnd(l2,n); 94 showData(l1, l2); 95 /** End ***********************************/ 96 } 97 /** 98 * Print the ListNode 99 * @param l1 ListNode 100 * @param l2 ListNode 101 */ 102 public static void showData(ListNode l1, ListNode l2){ 103 System.out.println("l1 -->"); 104 while (l1.next != null) { 105 System.out.print(l1.val + "\t"); 106 l1 = l1.next; 107 } 108 System.out.println(l1.val); 109 System.out.println("l2 -->"); 110 while (l2.next != null) { 111 System.out.print(l2.val + "\t"); 112 l2 = l2.next; 113 } 114 System.out.println(l2.val); 115 System.out.println("/************************************/"); 116 } 117 } 118 119 //Definition for singly-linked list. 120 class ListNode { 121 int val; 122 ListNode next; 123 ListNode(int x) { val = x; } 124 }
输出：
input List l1 and l2
l1 -->
0 2 4 6 8 10
l2 -->
1 3 5 7 9
/************************************/
mergeTwoLists(l1, l2) -->
0 1 2 3 4 5 6 7 8 9 10
After merge
l1 -->
0 1 2 3 4 5 6 7 8 9 10
l2 -->
1 2 3 4 5 6 7 8 9 10
/************************************/
9
l1 -->
0 1 2 3 4 5 6 7 8 9
l2 -->
1 2 3 4 5 6 7 8 9
/************************************/
