面试题2.1：编写代码，移除未排序链表中的重复结点 进阶：如果不得使用临时缓冲区，该怎么解决？
package cc150;
import java.util.HashMap;
import java.util.Map;
public class DeleteDups {
public static void main(String[] args) {
// TODO 自动生成的方法存根
LinkedListNode Node0 = new LinkedListNode(1);
LinkedListNode Node1 = new LinkedListNode(1);
LinkedListNode Node2 = new LinkedListNode(2);
LinkedListNode Node3 = new LinkedListNode(3);
Node0.next = Node1;
Node1.next = Node2;
Node2.next = Node3;
deleteDups(Node0);
LinkedListNode temp = Node0;
while(temp != null){
System.out.println(temp.iData);
temp = temp.next;
}
}
// public static void deleteDups(LinkedListNode n){
// Map<Integer,Boolean> map = new HashMap<Integer,Boolean>();
// LinkedListNode pre = null; //记录上一次不重复的结点
// while(n != null){
// if(map.containsKey(n.iData)){
// pre.next = n.next;
// }else{
// map.put(n.iData, true);
// pre = n;
// }
// n = n.next;
// }
//
// }
public static void deleteDups(LinkedListNode head){
if(head == null)
return;
LinkedListNode current = head;
while(current != null){
LinkedListNode runner = current;
while(runner.next != null){ //是runner.next
if(runner.next.iData == current.iData) //判断内层所有结点是否等于外层结点
runner.next = runner.next.next;
else
runner = runner.next;
}
current = current.next;
}
}
}
面试题2.2：实现一个算法，找出单向链表中倒数第k个结点。——《剑指Offer》面试题15 (找出) &《Leetcode》removeNthNode （移除）
package cc150;
public class NthToLast {
public static void main(String[] args) {
// TODO 自动生成的方法存根
ListNode Node1 = new ListNode(1);
ListNode Node2 = new ListNode(2);
ListNode Node3 = new ListNode(3);
Node1.next = Node2;
Node2.next = Node3;
System.out.println(nthToLast(Node1,1).val);
}
public static ListNode nthToLast(ListNode head,int k){ //返回链表的倒数第k个结点
if(k <= 0)
return null;
ListNode p1 = head;
ListNode p2 = head;
for(int i=0;i<k-1;i++){
if(p2 == null)
return null;
p2 = p2.next;
}
if(p2 == null)
return null;
while(p2.next != null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
面试题2.3：实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
思路：因为是单向链表，所以不知道一个结点的前一个结点，所以当这个结点是最后一个的时候，无解
只要把要删除的结点的下一个结点的数据复制到这个结点即可。
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 nextNode = pNode.next;//取得要删除结点的下一个结点
pNode.val = nextNode.val;
pNode.next = nextNode.next;
return true;
}
}
面试题2.4：编写代码，以给定值x为基准讲链表分割成两部分，所有小于x的结点排在大于或者等于x的结点之前。
package cc150;
public class Partition {
public static void main(String[] args) {
// TODO 自动生成的方法存根
ListNode Node1 = new ListNode(5);
ListNode Node2 = new ListNode(4);
ListNode Node3 = new ListNode(3);
ListNode Node4 = new ListNode(2);
ListNode Node5 = new ListNode(1);
Node1.next = Node2;
Node2.next = Node3;
Node3.next = Node4;
Node4.next = Node5;
ListNode temp = partition(Node1,3);
while(temp != null){
System.out.println(temp.val);
temp = temp.next;
}
}
public static ListNode partition(ListNode pHead, int x) {
// write code here
ListNode beforeStart = null; //记录链表的头结点
ListNode afterStart = null; //记录链表的头结点
ListNode beforeEnd = null;
ListNode afterEnd = null;
ListNode pNext = pHead;
while(pNext != null){
if(pNext.val < x){
if(beforeStart == null){
beforeStart = pNext;
beforeEnd = pNext;
}else{
beforeEnd.next = pNext;
beforeEnd = beforeEnd.next;
}
}else{
if(afterStart == null){
afterStart = pNext;
afterEnd = pNext;
}else{
afterEnd.next = pNext;
afterEnd = afterEnd.next;
}
}
pNext = pNext.next;
}
//切记断掉after最后一个元素的next，不然会形成环
if(afterEnd != null)
afterEnd.next = null;
//如果beforeStart为null，返回afterStart头结点
if(beforeStart == null)
return afterStart;
beforeEnd.next = afterStart;
return beforeStart;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
面试题2.5：给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
进阶：假设这些数位是正向存放的，请再做一遍。
package cc150;
import cc150.Partition.ListNode;
public class Plus {
public static void main(String[] args) {
// TODO 自动生成的方法存根
ListNode Node1 = new ListNode(7);
ListNode Node2 = new ListNode(2);
ListNode Node3 = new ListNode(3);
Node1.next = Node2;
Node2.next = Node3;
ListNode Node4 = new ListNode(4);
ListNode Node5 = new ListNode(5);
ListNode Node6 = new ListNode(6);
ListNode Node7 = new ListNode(7);
Node4.next = Node5;
Node5.next = Node6;
Node6.next = Node7;
ListNode temp = plusAB(Node1,Node4);
System.out.println(temp.val);
while(temp !=null){
System.out.print(temp.val);
temp = temp.next;
}
}
public static ListNode plusAB(ListNode a, ListNode b) {
// write code here
if(a == null && b == null)
return null;
int carry = 0;
ListNode result_temp = new ListNode(0);
ListNode result = result_temp;
while(a != null && b != null){
int value = a.val + b.val + carry;
if(value>=10){
result_temp.next = new ListNode(value-10);
carry = 1;
}else{
result_temp.next = new ListNode(value);
carry = 0;
}
result_temp = result_temp.next;
a = a.next;
b = b.next;
}
if(a != null){
result_temp.next = new ListNode(a.val+carry);
result_temp.next.next = a.next;
}
else if(b != null){
result_temp.next = new ListNode(b.val+carry);
result_temp.next.next = b.next;
}
else if(carry == 1){
result_temp.next = new ListNode(carry);
}
return result.next;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
面试题2.6：给定一个有环链表，实现一个算法返回环路的开头结点。
package cc150;
import cc150.Plus.ListNode;
public class FindBeginning {
public static void main(String[] args) {
// TODO 自动生成的方法存根
ListNode Node1 = new ListNode(1);
ListNode Node2 = new ListNode(2);
ListNode Node3 = new ListNode(3);
ListNode Node4 = new ListNode(4);
ListNode Node5 = new ListNode(5);
ListNode Node6 = new ListNode(6);
ListNode Node7 = new ListNode(7);
ListNode Node8 = new ListNode(8);
ListNode Node9 = new ListNode(9);
Node1.next = Node2;
Node2.next = Node3;
Node3.next = Node4;
Node4.next = Node5;
Node5.next = Node6;
Node6.next = Node7;
Node7.next = Node8;
Node8.next = Node9;
Node9.next = Node4;
System.out.println(findBeginning(Node1).val);
}
public static ListNode findBeginning(ListNode head){
ListNode slow = head;
ListNode fast = head;
//slow移动一步，fast移动两步，链表到头或者碰撞的时候停止
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
break;
}
//如果是链表到头，没有环路
if(fast == null || fast.next == null)
return null;
//将slow指向链表头部，fast指向碰撞处，两者同时移动，必回在环路起点相遇
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
}
面试题2.7： 编写一个函数，检查链表是否为回文。
CC150第一种解法：反转并比较
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {//反转并比较，CC150第一种解法
// write code here
if(pHead == null || pHead.next == null)
return true;
ListNode slow,fast; //快慢指针法查找链表的中心
slow = fast = pHead;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
if(fast != null){ //链表个数奇数个
slow.next = reverseList(slow.next);
slow = slow.next; //去掉中间的数
}else{
slow = reverseList(slow);
}
while(slow != null){
if(pHead.val != slow.val)
return false;
slow = slow.next;
pHead = pHead.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
if(head ==null){
return null;
}
Stack<ListNode> stack = new Stack<ListNode>();
ListNode current = head;
while(current != null){
stack.add(current);
current = current.next;
}
head = stack.pop();
current = head;
while(stack.empty() != true){
current.next = stack.pop();
current = current.next;
}
current.next = null; //Memory Limit Exceeded
return head;
}
}