JAVA面试链表总结.pdfVIP

JAVA 面试链表总结 1. package LinkedListSummary; 2. 3. import java.util.HashMap; 4. import java.util.Stack; 5. /** 6. * by Aaron 7. * 目录： 8. * 1. 求单链表中结点的个数: getListLength 9. * 2. 将单链表反转: reverseList （遍历），reverseListRec （递归） 10. * 3. 查找单链表中的倒数第 K 个结点（k 0 ）: reGetKthNode 11. * 4. 查找单链表的中间结点: getMiddleNode 12. * 5. 从尾到头打印单链表: reversePrintListStack ，reversePrintListRec （递归） 13. * 6. 已知两个单链表 pHead1 和 pHead2 各自有序，把它们合并成一个链表依然有 序: mergeSortedList, mergeSortedListRec 14. * 7. 判断一个单链表中是否有环: hasCycle 15. * 8. 判断两个单链表是否相交: isIntersect 16. * 9. 求两个单链表相交的第一个节点: getFirstCommonNode 17. * 10. 已知一个单链表中存在环，求进入环中的第一个节 点: getFirstNodeInCycle, getFirstNodeInCycleHashMap 18. * 11. 给出一单链表头指针 pHead 和一节点指针 pToBeDeleted ，O(1)时间复杂度删除节点 pToBeDeleted: delete 19. * 20. */ 21. public class Demo { 22. 23. public static void main(String[] args) { 24. Node n1 = new Node(1); 25. Node n2 = new Node(2); 26. Node n3 = new Node(3); 27. Node n4 = new Node(4); 28. Node n5 = new Node(5); 29. n1.next = n2; 30. n2.next = n3; 31. n3.next = n4; 32. n4.next = n5; 33. 34. printList(n1); 35. // System.out.println(getListLength(n1)); 36. // Node head = reverseList(n1); 37. // Node head = reverseListRec(n1); 38. // printList(head); 39. 40. Node x = reGetKthNode(n1, 2); 41. System.out.println(x.val); 42. reGetKthNodeRec(n1, 2); 43. 44. 45. // x = getMiddleNode(head); 46. // System.out.println(x.val); 47. // System.out.println(reversePrintListStack:); 48. // reversePrintListStack(head); 49. // System.out.println(reversePrintListRec:); 50. // reversePrintListRec(head); 51. 52. } 53. 54. 55. // public static void main(String[] args) { 56. // Node n1 = new Node(1); 57. //