“手撕”链表的九道OJ习题

目录

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;}
}