链表是面试中最常见的一种题型，因为他的每个题的代码短，短短的几行代码就可以体现出应聘者的编码能力，所以它也就成为了面试的重点。
链表常见的操作有1.打印链表的公共部分，2.删除链表的倒数第K个节点，3.翻转单向链表，4.环形约瑟夫环问题，5.判断链表是否是一个回文链表，6.两个链表生成相加链表，7.删除无序链表中重复出现的节点，8.删除指定值得节点，9.合并两个有序的单链表，10.环形链表的插入
import java.util.*; /********** *@Author:Tom-shushu *@Description:链表问题 *@Date:21:58 2019/10/2 * .--, .--, * ( ( .---./ ) ) * '.__/o o\__.' * {= ^ =} * > - < * / * // \ * //| . |\ * "' /'"_.-~^`'-. * _ /--' ` * ___)( )(___ * (((__) (__))) 高山仰止,景行行止.虽不能至,心向往之。 * **********/ public class Node { public int value; public Node head; public Node next; public Node(int data) { this.value = data; } //打印链表的公共部分 public void print(Node head1, Node head2) { while (head1 != null && head2 != null) { if (head1.value < head2.value) { head1 = head1.next; } else if (head1.value > head2.value) { head2 = head2.next; } else { System.out.println(head1.value); head1 = head1.next; head2 = head2.next; } } } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //删除单链表的倒数第K个节点 //版本一 public Node remove1(Node head, int k) { if (head == null || k < 1) { return head; } Node cur = head; while (cur != null) { k--; cur = cur.next; } if (k == 0) {//要删除的是第一个 head = head.next; } if (k < 0) { cur = head; while (++k != 0) { cur = cur.next; } cur.next = cur.next.next; } return head; } //版本二 public Node remove2(Node head, int k) { if (head == null || k <= 0) { return null; } Node slow = head; Node fast = head; //fast 指向 k + 1 for (int i = 1; i < k + 1; i++) { if (fast.next != null) { fast = fast.next; } else { return null; } } //fast指向尾部，slow指向倒数K+1，即 k 的前一个数。 while (fast.next != null) { fast = fast.next; slow = slow.next; } //删除第 k 个数。 slow = slow.next.next; return head; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //翻转单向链表 //版本一 public Node reList(Node head) { Node pre = null; Node next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } //版本二 public Node reList2(Node head) { if (head == null || head.next == null) { return head; } Node pre = head; Node newHead = null; while (pre != null) { Node temp = pre.next; pre.next = newHead; newHead = pre; pre = temp; } return newHead; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //环形约瑟夫问题 public Node yuesefu(Node head, int m) { if (head == null || head.next == head || m < 1) { return head; } Node last = head; while (last.next != head) { last = last.next; } int count = 0; while (head != last) { if (++count == m) { last.next = head.next; count = 0; } else { last = last.next; } head = last.next; } return head; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //判断一个链表是否是回文链表 public boolean isHuiWen(Node head) { Stack<Node> stack = new Stack<Node>(); Node cur = head; while (cur != null) { stack.push(cur); cur = cur.next; } while (head != null) { if (head.value != stack.pop().value) { return false; } head = head.next; } return true; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //两个单链表生成相加链表 public Node xinagjialainbiao(Node head1, Node head2) { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); while (head1 != null) { stack1.push(head1.value); head1 = head1.next; } while (head2 != null) { stack2.push(head1.value); head2 = head2.next; } int ca = 0; int n1 = 0; int n2 = 0; int n = 0; Node node = null; Node pre = null; while (!stack1.isEmpty() || !stack2.isEmpty()) { if (stack1.isEmpty()) { n1 = 0; } else { n1 = stack1.pop(); } if (stack2.isEmpty()) { n2 = 0; } else { n2 = stack2.pop(); } pre = node; node = new Node(n % 10); node.next = pre; } if (ca == 1) { pre = node; node = new Node(1); node.next = pre; } return node; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //删除无需单链表中重复出现的节点 public void deletecf(Node head) { if (head == null) { return; } HashSet<Integer> set = new HashSet<Integer>(); Node pre = head; Node cur = head.next; set.add(head.value); while (cur != null) { if (set.contains(cur.value)) { pre.next = cur.next; } else { set.add(cur.value); pre = cur; } cur = cur.next; } } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //在单链表中删除指定值得节点 public Node deletevalue(Node head, int num) { Stack<Node> stack = new Stack<Node>(); while (head != null) { if (head.value != num) { stack.push(head); } head = head.next; } while (!stack.isEmpty()) { stack.peek().next = head; head = stack.pop(); } return head; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //合并两个有序单链表(递归) public Node Merge(Node list1, Node list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } if (list1.value <= list2.value) { list1.next = Merge(list1.next, list2); return list1; } else { list2.next = Merge(list1, list2.next); return list2; } } //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++== //环形链表的插入 public Node insertNum(Node head,int num){ Node node = new Node(num); if(head == null){ node.next = node; return node; } Node pre = head; Node cur = head.next; while (cur != head){ if (pre.value <= num && cur.value >= num){ break; } pre = cur; cur = cur.next; } pre.next = node; node.next = cur; return head.value < num ? head : node; } }