做阿里巴巴网站公司,郑州高端模板建站,菜鸟是什么网站,怎么获得一个免费的域名题目
输入两个链表#xff0c;找出它们的第一个公共节点。
public static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val val;}
}分析
首先遍历两链表的长度。在第二次遍历的时候#xff0c;在较长的链表上先走若干步#xf…题目
输入两个链表找出它们的第一个公共节点。
public static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val val;}
}分析
首先遍历两链表的长度。在第二次遍历的时候在较长的链表上先走若干步步数为两链表之差的绝对值接着同时在两个链表遍历找到的第一个相同的节点就是它们的第一个公共节点。
放码
public class FindTheSameNode {public ListNode find(ListNode head1, ListNode head2) {int length1 count(head1);int length2 count(head2);int diff Math.abs(length1 - length2);ListNode pLong length1 length2 ? head1 : head2, pShort length1 length2 ? head2 : head1;while(diff 0) {pLong pLong.next;diff--;}while(pLong ! null pShort ! null pLong ! pShort) {pLong pLong.next;pShort pShort.next;}return pLong pShort ? pLong : null;}public int count(ListNode head) {int result 0;ListNode p head;while(p ! null) {result;p p.next;}return result;}}测试
import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.SinglyLinkedList.ListNode;public class FindTheSameNodeTest {private static ListNode list1;private static ListNode list2;private static ListNode same;static {same new ListNode(6);same.next new ListNode(7);list1 new ListNode(1);list1.next new ListNode(2);list1.next.next new ListNode(3);list1.next.next.next same;list2 new ListNode(4);list2.next new ListNode(5);list2.next.next same;}Testpublic void testFind() { FindTheSameNode fn new FindTheSameNode();assertEquals(6, fn.find(list1, list2).val);assertEquals(same, fn.find(list1, list2));}Testpublic void testCount() {FindTheSameNode fn new FindTheSameNode();assertEquals(5, fn.count(list1));assertEquals(4, fn.count(list2));}}
