正文
Cracking the Coding Interview 第二章
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
2.2 链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
思路：快慢指针(error: 判断是否有可行解，否则返回null, while, if 后加空格)
/*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null){
return null;
}
ListNode fast = head;
ListNode ans = head;
for (int i = 0; i < k; i++){
if (fast == null){
return null;
}
fast = fast.next;
}
while (fast != null){
fast = fast.next;
ans = ans.next;
}
return ans;
}
}
2.3 删除当前节点
实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true
思路：将当前的val转为下一个的val，释放下一个即可。
import java.util.*; /*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Remove {
public boolean removeNode(ListNode pNode) {
// write code here
if (pNode == null || pNode.next == null){
return false;
}
//ListNode next = pNode.next;
pNode.val = pNode.next.val;
pNode.next = pNode.next.next;
return true;
}
}
2.4 链表分割（小于x的在一边。大于等于x的又在一边）
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。
思路：（1）在原链表上找到第一个大的，将之后的小的往前移（error：移完之后不能立即向前，不然会错过连着的两个这种情况）
import java.util.*; /*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if (pHead == null){
return null;
}
ListNode front = new ListNode(0);
front.next = pHead;
pHead = front;
while (pHead.next != null && pHead.next.val < x){
pHead = pHead.next;
}
if (pHead.next != null){
ListNode greater = pHead.next;
while (greater.next != null){
if (greater.next.val < x){
ListNode temp = greater.next;
greater.next = temp.next;
temp.next = pHead.next;
pHead.next = temp;
pHead = temp;
} else {
greater = greater.next;
}
}
}
pHead = front.next;
front = null;
return pHead;
}
}
（2）新建两个链表small large，指向对应元素即可。时间复杂度更大。
import java.util.*; /*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
/*if (pHead == null){
return null;
}
ListNode front = new ListNode(0);
front.next = pHead;
pHead = front;
while (pHead.next != null && pHead.next.val < x){
pHead = pHead.next;
}
if (pHead.next != null){
ListNode greater = pHead.next;
while (greater.next != null){
if (greater.next.val < x){
ListNode temp = greater.next;
greater.next = temp.next;
temp.next = pHead.next;
pHead.next = temp;
pHead = temp;
} else {
greater = greater.next;
}
}
}
pHead = front.next;
front = null;
return pHead;*/
ListNode small = new ListNode(0);
ListNode large = new ListNode(0);
ListNode tailSmall = small;
ListNode tailLarge = large;
while (pHead != null){
if (pHead.val < x){
tailSmall.next = new ListNode(pHead.val);
tailSmall = tailSmall.next;
} else {
tailLarge.next = new ListNode(pHead.val);
tailLarge = tailLarge.next;
}
pHead = pHead.next;
}
tailSmall.next = large.next;
return small.next;
}
}
