网站信管局备案wordpress 主题小工具
目录
1. 第一题
2. 第二题
3. 第三题
4. 第四题
5. 第五题
6. 第六题
7. 第七题
8. 第八题
9. 第九题
1. 第一题
删除链表中等于给定值 val 的所有节点。OJ链接
思路如下：
相当于链表的removeAll();制定prev和cur，prev记录前一个节点，方便删除。
但是要注意head==null和head.val==val的时候
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。我们假设他们距离为N，fast快一步，所以每次都缩短1步，到0之后就相遇了。如下图：
如果fast一次走三步，还能相遇吗？那么他们每走一步追2，如下图：
9. 第九题
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL OJ链接
思路如下：
如果快慢指针，快指针走2步，慢指针走1步，她两相遇了，说明有环，这时候我们让快指针重新出发（fast=head），他和慢指针现在以相同的速度前行，当他们再次相遇的时候，就是出口！
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;}
}