• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

    请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中,每个结点除了有一个next 域指向下一个结点外,还有一个sibling 指向链表中的任意结点或者null。

    二、解题思路

    在不用辅助空间的情况下实现O(n)的时间效率。

    第一步:仍然是根据原始链表的每个结点N 创建对应的N’。把N’链接在N的后面。

    第二步:设置复制出来的结点的sibling。假设原始链表上的N的sibling指向结点S,那么其对应复制出来的N’是N的next指向的结点,同样S’也是S的next指向的结点。

    第三步:把这个长链表拆分成两个链表。把奇数位置的结点用next .
    链接起来就是原始链表,把偶数位置的结点用next 链接起来就是复制
    出来的链表。

    三、解题代码

    1. public class Test {
    2. /**
    3. * 复杂链表结点
    4. */
    5. public static class ComplexListNode {
    6. int value;
    7. ComplexListNode next;
    8. ComplexListNode sibling;
    9. }
    10. /**
    11. * 实现函复制一个复杂链表。在复杂链表中,每个结点除了有一个next字段指向下一个结点外,
    12. * 还有一个sibling字段指向链表中的任意结点或者NULL
    13. *
    14. * @param head 链表表头结点
    15. * @return 复制结点的头结点
    16. */
    17. public static ComplexListNode clone(ComplexListNode head) {
    18. // 如果链表为空就直接返回空
    19. if (head == null) {
    20. return null;
    21. }
    22. // 先复制结点
    23. cloneNodes(head);
    24. // 再链接sibling字段
    25. connectNodes(head);
    26. // 将整个链表拆分,返回复制链表的头结点
    27. return reconnectNodes(head);
    28. }
    29. /**
    30. * 复制一个链表,并且将复制后的结点插入到被复制的结点后面,只链接复制结点的next字段
    31. *
    32. * @param head 待复制链表的头结点
    33. */
    34. public static void cloneNodes(ComplexListNode head) {
    35. // 如果链表不空,进行复制操作
    36. while (head != null) {
    37. // 创建一个新的结点
    38. ComplexListNode tmp = new ComplexListNode();
    39. // 将被复制结点的值传给复制结点
    40. tmp.value = head.value;
    41. // 复制结点的next指向下一个要被复制的结点
    42. tmp.next = head.next;
    43. // 被复制结点的next指向复制结点
    44. head.next = tmp;
    45. // 到些处就已经完成了一个结点的复制并且插入到被复制结点的后面
    46. // heed指向下一个被复制结点的位置
    47. head = tmp.next;
    48. }
    49. }
    50. /**
    51. * 设置复制结点的sibling字段
    52. *
    53. * @param head 链表的头结
    54. */
    55. public static void connectNodes(ComplexListNode head) {
    56. // 如链表不为空
    57. while (head != null) {
    58. // 当前处理的结点sibling字段不为空,则要设置其复制结点的sibling字段
    59. if (head.sibling != null) {
    60. // 复制结点的sibling指向被复制结点的sibling字段的下一个结点
    61. // head.next:表求复制结点,
    62. // head.sibling:表示被复制结点的sibling所指向的结点,
    63. // 它的下一个结点就是它的复制结点
    64. head.next.sibling = head.sibling.next;
    65. }
    66. // 指向下一个要处理的复制结点
    67. head = head.next.next;
    68. }
    69. }
    70. /**
    71. * 刚复制结点和被复制结点拆开,还原被复制的链表,同时生成复制链表
    72. *
    73. * @param head 链表的头结点
    74. * @return 复制链表的头结点
    75. */
    76. public static ComplexListNode reconnectNodes(ComplexListNode head) {
    77. // 当链表为空就直接返回空
    78. if (head == null) {
    79. return null;
    80. }
    81. // 用于记录复制链表的头结点
    82. ComplexListNode newHead = head.next;
    83. // 用于记录当前处理的复制结点
    84. ComplexListNode pointer = newHead;
    85. // 被复制结点的next指向下一个原链表结点
    86. head.next = newHead.next;
    87. // 指向新的被复制结点
    88. head = head.next;
    89. while (head != null) {
    90. // pointer指向复制结点
    91. pointer.next = head.next;
    92. pointer = pointer.next;
    93. // head的下一个指向复制结点的下一个结点,即原来链表的结点
    94. head.next = pointer.next;
    95. // head指向下一个原来链表上的结点
    96. head = pointer.next;
    97. }
    98. // 返回复制链表的头结点
    99. return newHead;
    100. }
    101. }