目录
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 here
ListNode 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 here
if (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;
}
}
