个人认为，算法是程序员的内功，不管你是能把 Java 或是 C # 玩出花来，也是需要注意提升一下内在修炼的。毕竟，只有深厚的内功才能把招式发挥到极致。以下算法，可能咋一看觉得很简单，自己也能实现，但是要知道能实现功能固然重要，但算法的效率更值得研究。纸上得来终觉浅，相信如果你能把以下算法都亲手实现一遍，必定会有收获，至少我个人是这样。
想要实现以下将介绍算法，首先需要自己实现一个 链表，下面粘贴上我利用前插法写的链表。
public class MyList {
private Node first;
public MyList(){
}
public class Node {
Node next;
int data;
public Node(Node next, int data) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
this.next = null;
}
public Node(){
}
}
public void add(int data) {
first = add(first, data);
}
private Node add(Node x, int data) {
if (x == null)
return new Node(data);
return new Node(x, data);
}
public Node getFirst() {
return first;
}
}
2.1 编写代码，移除未排序链表中的重复结点。如果不能使用缓冲区，又该怎么解决？
// 借用临时缓冲区的解法
public static void deleteSame(MyList list) {
MyList.Node current = list.getFirst();
MyList.Node pre = null;
Hashtable<Integer, Boolean> hashtable = new Hashtable<>();
while (current != null) {
if (hashtable.containsKey(current.data)) {
pre.next = current.next;
} else {
hashtable.put(current.data, true);
pre = current;
}
current = current.next;
}
}
// 不借用临时缓冲区
public static void deleteSameTwo(MyList list) {
MyList.Node current = list.getFirst();
MyList.Node runner;
while (current != null) {
runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
}
runner = runner.next;
}
current = current.next;
}
}
2.2 实现一个算法，找出单链表中倒数第 k 个结点．
// 只打印该元素，不返回该元素
private static int findOne(MyList.Node node, int k) {
if (node == null)
return 0;
int i = findOne(node.next, k) + 1;
if (i == k)
System.out.println(node.data);
return i;
}
// 基于以上方法 利用 IntWrapper返回该元素
private class IntWrapper {
public int value = 0;
}
private static MyList.Node findTwo(MyList.Node node, int k, IntWrapper i) {
if (node == null)
return null;
MyList.Node t = findTwo(node.next, k, i);
i.value = i.value + 1;
if (i.value == k) {
return node;
}
return t;
}
注意除了以上两种算法，还有一种方法，就是设置两个指针，一个是快指针，一个是慢指针，先让快指针向前移动 ｋ－１ 次，也就是移动到 第 ｋ 个元素，然后让 慢指针开始移动，这样的话当快指针指到末尾的时候，慢指针指向的刚好是 倒数第 ｋ 个元素。
2.3 实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
private static void delete(Node root) {
// 如果当前节点为空或者当前节点为尾节点的时候直接退出
if (root == null || root.next == null) {
return;
}
Node next = root.next;
root.data = next.data;
root.next = next.next;
}
2.4 编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的节点之前。
public static Node divide(Node root, int x) {
MyList mins = new MyList();
MyList maxs = new MyList();
while (root != null) {
if (root.data < x) {
mins.add(root.data);
} else {
maxs.add(root.data);
}
root = root.next;
}
Node minRoot = mins.getFirst();
Node maxRoot = maxs.getFirst();
if (minRoot == null) {
return maxRoot;
}
Node temp = minRoot;
while (minRoot.next != null)
minRoot = minRoot.next;
minRoot.next = maxRoot;
return temp;
}
2.5 给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对两个整数求和，并用链表形式返回结果。
public static Node addLists(Node n1, Node n2, int carry) {
if (n1 == null && n2 == null && carry == 0) {
return null;
}
Node result = new MyList().new Node();
int value = carry;
if (n1 != null) {
value += n1.data;
}
if (n2 != null) {
value += n2.data;
}
result.data = value % 10;
Node more = addLists(n1 == null ? null : n1.next, n2 == null ? null : n2.next, value / 10);
result.next = more;
return result;
}
2.6 编写一个函数，检查链表是否为回文。
public static boolean isPalindrome(Node root) {
Node fast = root;
Node slow = root;
Stack<Integer> stack = new Stack<>();
while (fast != null && fast.next != null) {
stack.push(slow.data);
slow = slow.next;
fast = fast.next.next;
}
// 说明有奇数个元素，跳过中间元素
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
int top = stack.pop().intValue();
if (top != slow.data)
return false;
slow = slow.next;
}
return true;
}
以上代码实现都是核心代码，需要完整代码的 点击此处
网友评论