对亚马逊网站做简要分析与评价,移动网站开发源代码,深圳网站建设网页设计,vps 网站备案目录
1. 第一题
2. 第二题
3. 第三题
4. 第四题
5. 第五题
6. 第六题
7. 第七题
8. 第八题
9. 第九题 1. 第一题
删除链表中等于给定值 val 的所有节点。OJ链接 思路如下#xff1a; 相当于链表的removeAll();制定prev和cur#xff0c;prev记录前一个节点#xff…
目录
1. 第一题
2. 第二题
3. 第三题
4. 第四题
5. 第五题
6. 第六题
7. 第七题
8. 第八题
9. 第九题 1. 第一题
删除链表中等于给定值 val 的所有节点。OJ链接 思路如下 相当于链表的removeAll();制定prev和curprev记录前一个节点方便删除。 但是要注意headnull和head.valval的时候 public ListNode removeElements(ListNode head, int val) {if (head null) {return head;}ListNode cur head.next;ListNode prev head;while (cur ! null) {if (cur.val val) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}}if (head.val val) {head head.next;}return head;}
2. 第二题
反转一个单链表。OJ链接 思路如下 头插法把后面的头插到前面 public ListNode reverseList(ListNode head) {if (head null) {return head;}ListNode cur head.next;head.next null;while (cur ! null) {ListNode curN cur.next;cur.next head;head cur;cur curN;}return head;}3. 第三题
给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。OJ链接 思路如下 快慢指针快指针走2步慢指针走1步当快指针走完慢指针刚刚好走一半 public ListNode middleNode(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
4. 第四题
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接 思路如下 定义一个傀儡头节点和tmp让headA和headB去比较如果谁小tmp就跟在谁的后面然后head小的直到一个链表为空 public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newH new ListNode(0);ListNode tmp newH;while (headA ! null headB ! null) {if (headA.val headB.val) {tmp.next headA;headA headA.next;} else {tmp.next headB;headB headB.next;}tmp tmp.next;}if (headA null) {tmp.next headB;}if (headB null) {tmp.next headA;}return newH.next;}
5. 第五题
写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。OJ链接 思路如下 两个链表一个小链表头节点as尾节点ae一个大链表头节点bs尾节点be小于x放小链表大于x放大链表。然后让ae指向bs把两个连接起来 public ListNode partition(ListNode pHead, int x) {// write code hereListNode as null;ListNode ae null;ListNode bs null;ListNode be null;ListNode cur pHead;while (cur ! null) {if (cur.val x) {if (as null) {as ae cur;} else {ae.next cur;ae ae.next;}} else {if (bs null) {bs be cur;} else {be.next cur;be be.next;}}cur cur.next;}if (as null) {return bs;}ae.next bs;if (bs ! null) {be.next null;}return as;}
6. 第六题
链表的回文结构。OJ链接 思路如下 用快慢指针找出中间节点然后把后面的节点进行头插最后头和尾开始比较val值相不相同 public boolean chkPalindrome(ListNode A) {// write code hereif (A null) {return true;}ListNode slow A;ListNode fast A;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}ListNode cur slow.next;while (cur ! null) {ListNode curN cur.next;cur.next slow;slow cur;cur curN;}while (A ! slow) {if (A.val ! slow.val) {return false;}if (A.next slow) {return true;}A A.next;slow slow.next;}return true;}7. 第七题
输入两个链表找出它们的第一个公共结点。OJ链接 思路如下 两条链表定义p1和p2求出每条链表的长度然后相减得出多出来的距离把多出来的距离让长的链表先走。然后两个节点一起走相遇的点就是公共的第一个节点 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 headA;ListNode p2 headB;int lenA 0;int lenB 0;while (p1 ! null) {lenA;p1 p1.next;}while (p2 ! null) {lenB;p2 p2.next;}int len lenA - lenB;p1 headA;p2 headB;if (len 0) {p1 headB;p2 headA;len lenB - lenA;}while (len ! 0) {p1 p1.next;len--;}while (p1 ! p2) {p1 p1.next;p2 p2.next;}if (p1 null) {return null;}return p1;}
8. 第八题
给定一个链表判断链表中是否有环。OJ链接 思路如下 快慢指针快的走两步慢的走一步。也就是快的先进圈如果他俩相遇了就说明有环假设没环的话快的先进去早就空指针null了 public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {return true;}}return false;} 相遇的原理 因为fast走得快slow走得慢。所以fast先进环slow后进环我们可以看成fast进了环之后再追slow。我们假设他们距离为Nfast快一步所以每次都缩短1步到0之后就相遇了。如下图 如果fast一次走三步还能相遇吗那么他们每走一步追2如下图 9. 第九题
给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL OJ链接 思路如下 如果快慢指针快指针走2步慢指针走1步她两相遇了说明有环这时候我们让快指针重新出发fasthead他和慢指针现在以相同的速度前行当他们再次相遇的时候就是出口 public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {break;}}if (fast null || fast.next null) {return null;}fast head;while (fast ! slow) {fast fast.next;slow slow.next;}return fast;}
}
