重温数据结构和算法 LinkedList 2019-03-02 有关链表常考面试题:单链表反转、检测链表中的环、有序链表合并、删除链表倒数第 k 个结点、求链表中间结点 123456789public static class Node { private int data; private Node next; public Node(int data) { this.data = data; }} 单链表反转123456789101112131415161718// 单链表反转 方法一:非递归方法public Node reverse(Node head) { Node preNode = null; Node curNode = head; Node newhead = null; while (curNode != null) { Node nextNode = curNode.next; if (nextNode == null) { newhead = curNode; } curNode.next = preNode; preNode = curNode; curNode = nextNode; } return newhead;} 12345678910// 单链表反转 方法二:递归方法public Node diguiReverse(Node head) { if (head == null || head.next == null) return head; Node newhead = diguiReverse(head.next); head.next.next = head; head.next = null; return newhead;} 链表中环的检测123456789101112131415// 链表中环的检测 快慢指针法public boolean checkCircle(Node head) { if (head == null) return false; Node fast = head; Node slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) return true; } return false;} 两个有序链表的合并12345678910111213141516// 两个有序链表的合并 递归法public Node mergeSortedLinkLists(Node la, Node lb) { if (la == null) return lb; if (lb == null) return la; Node newHead = null; if (la.data < lb.data) { newHead = la; newHead.next = mergeSortedLinkLists(la.next, lb); } else { newHead = lb; newHead.next = mergeSortedLinkLists(lb.next, la); } return newHead;} 删除链表倒数第n个结点12345678910111213141516171819202122// 删除链表倒数第n个结点;快慢指针法找到倒数第 k 个结点的前一个结点,即倒数 k + 1 个结点public Node deleteLastKth(Node head, int k) { if (head == null || k < 1) return null; Node fast = head; Node slow = head; for (int i = 0; i < (k + 1 ) - 1; ++i) { if (fast.next != null) fast = fast.next; else { return null; } } while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head;} 求链表的中间结点12345678910111213// 求链表的中间结点public Node findMiddleNode(Node head) { if (head == null) return null; Node fast = head; Node slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow;} 赏 谢谢你请Leo吃糖果哦 支付宝 微信 数据结构与算法 扫一扫,分享到微信