@H_403_5@import java.util.*; /********** *@Author:Tom-shushu *@Description:链表问题 *@Date:21:58 2019/10/2 * .--,.--,* ( ( \.---./ ) ) * '.__/o o\__.' * {= ^ =} * > - < * / \ * // \\ * //| . |\\ * "'\ /'"_.-~^`'-. * \ _ /--' ` * ___)( )(___ * (((__) (__))) 高山仰止,景行行止.虽不能至,心向往之。 * **********/ public class Node { int value; public Node head; Node next; public Node( data) { this.value = data; } //打印链表的公共部分 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, k) { if (head == null || k < 1return head; } Node cur = head; while (cur != ) { 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; } head; } 版本二 public Node remove2(Node head,1)">null || k <= 0return ; } Node slow = head; Node fast =fast 指向 k + 1 for (int i = 1; i < k + 1; i++if (fast.next != ) { fast = fast.next; } { ; } } fast指向尾部，slow指向倒数K+1，即 k 的前一个数。 while (fast.next != ) { fast = fast.next; slow = slow.next; } 删除第 k 个数。 slow = slow.next.next; +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 翻转单向链表 Node reList(Node head) { Node pre = ; Node next = ; while (head != ) { next = head.next; head.next = pre; pre = head; head = next; } pre; } Node reList2(Node head) { null || head.next == head; } Node pre = head; Node newHead = while (pre != ) { Node temp = pre.next; pre.next = newHead; newHead = temp; } newHead; } 环形约瑟夫问题 public Node yuesefu(Node head,1)"> m) { null || head.next == head || m < 1 head; } Node last =while (last.next != head) { last = last.next; } int count = 0while (head != last) { if (++count == m) { last.next = head.next; count = 0; } { last = last.next; } head =判断一个链表是否是回文链表 boolean isHuiWen(Node head) { Stack<Node> stack = new Stack<Node>(); Node cur =) { stack.push(cur); cur =if (head.value != stack.pop().value) { false; } head =true; } +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 两个单链表生成相加链表 Node xinagjialainbiao(Node head1,Node head2) { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = (); ) { stack1.push(head1.value); head1 = head1.next; } while (head2 != ) { stack2.push(head1.value); head2 = head2.next; } int ca = 0int n1 = 0int n2 = 0int n = 0; Node node = ; Node pre = while (!stack1.isEmpty() || !stack2.isEmpty()) { if (stack1.isEmpty()) { n1 = 0 { n1 = stack1.pop(); } (stack2.isEmpty()) { n2 = 0 { n2 = stack2.pop(); } pre = node; node = new Node(n % 10); node.next = pre; } if (ca == 1) { pre =new Node(1 node; } 删除无需单链表中重复出现的节点 deletecf(Node head) { ; } HashSet<Integer> set = new HashSet<Integer>(); Node pre = head; Node cur = head.next; set.add(head.value); (set.contains(cur.value)) { pre.next = cur.next; } { set.add(cur.value); pre = cur; } cur = cur.next; } } 在单链表中删除指定值得节点 public Node deletevalue(Node head,1)"> num) { Stack<Node> stack = num) { stack.push(head); } head =while (!stack.isEmpty()) { stack.peek().next = stack.pop(); } 合并两个有序单链表(递归) Node Merge(Node list1,Node list2) { if (list1 == list2; } if (list2 == list1; } if (list1.value <= list2.value) { list1.next = Merge(list1.next,list2); list1; } { list2.next = Merge(list1,list2.next); list2; } } ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++== 环形链表的插入 public Node insertNum(Node head,1)"> num){ Node node = new Node(num); if(head == ){ node.next = node; node; } Node pre = 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; } }