定义一个函数在O时间删除该节点,在复杂链表中

这样在第二部连接sibling结点的时候就可以以O(1)的时间复杂度定位到相应的sibling节点,由于定位每个节点的silbing节点都需要从链表的头结点开始经过O(n)步才能实现,这样在第二部连接sibling结点的时候就可以以O(1)的时间复杂度定位到相应的sibling节点,由于定位每个节点的silbing节点都需要从链表的头结点开始经过O(n)步才能实现,如果要删除的节点是链表的尾节点的话,把后面的节点的内容复制到当前节点处,此时再删除节点j,然后把i的指针指向节点j的下一个节点,每个结点除了有一个m,pSibling指向链表中的任意结点或者NULL.

剑指offer面试题26:复杂链表的复制,剑指offer

题目:请实现一个函数,复制一个复杂链表。

在复杂链表中,每个结点除了有一个next指针指向下一个结点外,还有一个sibling指针指向链表中的任意结点或者nulL

直观解法:

1.遍历链表,复制链表节点,并连接next节点。2.遍历链表,连接sibling节点。对于一个有n个节点的链表,由于定位每个节点的silbing节点都需要从链表的头结点开始经过O(n)步才能实现,因此这种方法的时间复杂度是O(n2)

优化解法:上述方法的时间主要是用在了sibling节点的定位上,考虑优化此步骤。具体的做法是在复制节点的时候,把原节点N和复制出来的N’节点用一个map保存起来,这样在第二部连接sibling结点的时候就可以以O(1)的时间复杂度定位到相应的sibling节点,总体时间复杂度为O(n),空间复杂度也是O(n)

最优算法:

第一步:根据原始链表的每个节点创建对应的复制结点,把复制结点连接在原结点的后面
第二步:设置复制出来的结点的任意结点sibling节点
第三步:把长链表拆分成两个链表

  1 package Solution;
  2 
  3 public class No26CopyComplexList {
  4 
  5     static class ComplexListNode{
  6         int value;
  7         ComplexListNode next;
  8         ComplexListNode sibling;
  9         public ComplexListNode(){
 10             
 11         }
 12         public ComplexListNode(int value,ComplexListNode next,ComplexListNode sibling){
 13             this.value=value;
 14             this.next=next;
 15             this.sibling=sibling;
 16         }
 17     }
 18     
 19     //把复杂链表中的所有结点进行复制,并连接在原结点的后面
 20     private static void cloneNode(ComplexListNode head){
 21         ComplexListNode node=head;
 22         while(node!=null){
 23             ComplexListNode clonedNode=new ComplexListNode();
 24             clonedNode.value=node.value;
 25             clonedNode.next=node.next;
 26             clonedNode.sibling=null;
 27             node.next=clonedNode;
 28             node=clonedNode.next;
 29         }
 30     }
 31     //设置复制的节点的指向任意结点的连接关系
 32     private static void connectSiblingNodes(ComplexListNode head){
 33         ComplexListNode node=head;
 34         while(node!=null){
 35             ComplexListNode clonedNode=node.next;
 36             if(node.sibling!=null){
 37                 clonedNode.sibling=node.sibling.next;
 38             }
 39             node=clonedNode.next;
 40         }
 41     }
 42     //把长链表拆分成两个单独的链表,并返回复制后的链表的头结点
 43     private static ComplexListNode reconnectNodes(ComplexListNode head){
 44         ComplexListNode node=head;
 45         ComplexListNode clonedHead=null;
 46         ComplexListNode clonedNode=null;
 47         if(node!=null){
 48             clonedHead=clonedNode=node.next;
 49             node.next=clonedNode.next;
 50             node=clonedNode.next;
 51         }
 52         while(node!=null){
 53             clonedNode.next=node.next;
 54             clonedNode=node.next;
 55             node.next=clonedNode.next;
 56             node=clonedNode.next;
 57         }
 58         return clonedHead;
 59     }
 60     public static ComplexListNode copyComplexList(ComplexListNode head){
 61         if(head==null)
 62             return null;
 63         cloneNode(head);
 64         connectSiblingNodes(head);
 65         return reconnectNodes(head);
 66     }
 67     
 68     public static void printComplexList(ComplexListNode head){
 69         ComplexListNode node=head;
 70         int  value=0;
 71         ComplexListNode next=null;
 72         ComplexListNode sibling=null;
 73         while(node!=null){
 74             value=node.value;
 75             next=node.next;
 76             sibling=node.sibling;
 77             StringBuilder sb=new StringBuilder("当前节点的值为:").append(value);
 78             if(next!=null)
 79                 sb.append(",下一结点的值为:").append(next.value);
 80             else
 81                 sb.append(",当前结点为尾节点");
 82             if(sibling!=null)
 83                 sb.append(",指向任意结点的值为:").append(sibling.value);
 84             else
 85                 sb.append(",没有指向其他结点的任意结点");
 86             System.out.println(sb.toString());    
 87             node=node.next;
 88         }
 89     }
 90     public static void main(String[] args) {
 91         ComplexListNode node1=new ComplexListNode();
 92         ComplexListNode node2=new ComplexListNode();
 93         ComplexListNode node3=new ComplexListNode();
 94         ComplexListNode node4=new ComplexListNode();
 95         ComplexListNode node5=new ComplexListNode();
 96         node1.value=1;
 97         node1.next=node2;
 98         node1.sibling=node3;
 99         node2.value=2;
100         node2.next=node3;
101         node2.sibling=node5;
102         node3.value=3;
103         node3.next=node4;
104         node3.sibling=null;
105         node4.value=4;
106         node4.next=node5;
107         node4.sibling=node2;
108         node5.value=5;
109         node5.next=null;
110         node5.sibling=null;
111         printComplexList(node1);
112         System.out.println("=========================开始复制============================");
113         printComplexList(copyComplexList(node1));
114     }
115 }

 

题目:请实现一个函数,复制一个复杂链表。
在复杂链表中,每个结点除了有一个next指针指…

直观解法:

剑指offer编程题Java实现——面试题13在O(1)时间内删除链表节点,剑指offer

题目:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。

由于给定的是单向链表,正常删除链表的时间复杂度是查找链表的时间复杂度即O(n),如果要求在O(1)时间复杂度内删除节点,通过遍历链表找到该节点的上一节点和下一节点的方法是行不通了。所以实现的思路是,根据给定的要删除的节点,可以直接找到其后年的节点,把后面的节点的内容复制到当前节点处,同时将当前节点指向其后面节点的后面节点保证链表不断开,再把下一节点删掉就相当于把给定的节点删除了。

需要考虑到的一点是,如果要删除的节点是链表的尾节点的话,那还是需要从头结点按照顺序遍历到尾节点的前一节点,然后删除尾节点,总的平均时间复杂度就是[(n-1)*1+O(n)]/n,结果还是O(1)。

 

 1 /**
 2  * 剑指offer面试题13:在O(1)时间删除链表节点
 3  * 题目:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。
 4  * @author GL
 5  *
 6  */
 7 public class No13DeleteNodeInList {
 8 
 9     public static class ListNode{
10         public int data;
11         public ListNode next;
12         public ListNode(int data,ListNode next){
13             this.data=data;
14             this.next=next;
15         }
16     }
17 
18     public static void deleteNode(ListNode head,ListNode node){
19         //删除尾节点,采用顺序查找找到尾节点的前一节点
20         if(node.next==null){
21             while(head.next!=node){
22                 head=head.next;
23             }
24             head.next=null;
25         }
26         //要删除的节点是头结点
27         else if(head==node){
28             head=null;
29         }
30         //要删除的节点是中间普通节点
31         else{
32             node.data=node.next.data;
33             node.next=node.next.next;
34         }
35     }
36     public static void main(String[] args) {
37         ListNode tail=new ListNode(1,null);
38         ListNode c=new ListNode(2,tail);
39         ListNode b=new ListNode(3,c);
40         ListNode head=new ListNode(4,b);
41         deleteNode( head,c);
42         while(head!=null){
43             System.out.println(head.data);
44             head=head.next;
45         }
46 
47     }
48 }

 

题目:给定单向链表的头指针和一个节点指针,定义一个函数在…

[剑指offer] 链表中倒数第k个结点

解法二:
解法一的时间复杂度主要耗费在m_pSibling复制过程中需要遍历,而避免遍历的方法之一就是hash表,因此可以考虑建立一个原结点N和新结点N’的映射关系,这样在复制m_pSibling的时候,在新链表中寻找结点时直接查表即可。

  1 package Solution;
  2 
  3 public class No26CopyComplexList {
  4 
  5     static class ComplexListNode{
  6         int value;
  7         ComplexListNode next;
  8         ComplexListNode sibling;
  9         public ComplexListNode(){
 10             
 11         }
 12         public ComplexListNode(int value,ComplexListNode next,ComplexListNode sibling){
 13             this.value=value;
 14             this.next=next;
 15             this.sibling=sibling;
 16         }
 17     }
 18     
 19     //把复杂链表中的所有结点进行复制,并连接在原结点的后面
 20     private static void cloneNode(ComplexListNode head){
 21         ComplexListNode node=head;
 22         while(node!=null){
 23             ComplexListNode clonedNode=new ComplexListNode();
 24             clonedNode.value=node.value;
 25             clonedNode.next=node.next;
 26             clonedNode.sibling=null;
 27             node.next=clonedNode;
 28             node=clonedNode.next;
 29         }
 30     }
 31     //设置复制的节点的指向任意结点的连接关系
 32     private static void connectSiblingNodes(ComplexListNode head){
 33         ComplexListNode node=head;
 34         while(node!=null){
 35             ComplexListNode clonedNode=node.next;
 36             if(node.sibling!=null){
 37                 clonedNode.sibling=node.sibling.next;
 38             }
 39             node=clonedNode.next;
 40         }
 41     }
 42     //把长链表拆分成两个单独的链表,并返回复制后的链表的头结点
 43     private static ComplexListNode reconnectNodes(ComplexListNode head){
 44         ComplexListNode node=head;
 45         ComplexListNode clonedHead=null;
 46         ComplexListNode clonedNode=null;
 47         if(node!=null){
 48             clonedHead=clonedNode=node.next;
 49             node.next=clonedNode.next;
 50             node=clonedNode.next;
 51         }
 52         while(node!=null){
 53             clonedNode.next=node.next;
 54             clonedNode=node.next;
 55             node.next=clonedNode.next;
 56             node=clonedNode.next;
 57         }
 58         return clonedHead;
 59     }
 60     public static ComplexListNode copyComplexList(ComplexListNode head){
 61         if(head==null)
 62             return null;
 63         cloneNode(head);
 64         connectSiblingNodes(head);
 65         return reconnectNodes(head);
 66     }
 67     
 68     public static void printComplexList(ComplexListNode head){
 69         ComplexListNode node=head;
 70         int  value=0;
 71         ComplexListNode next=null;
 72         ComplexListNode sibling=null;
 73         while(node!=null){
 74             value=node.value;
 75             next=node.next;
 76             sibling=node.sibling;
 77             StringBuilder sb=new StringBuilder("当前节点的值为:").append(value);
 78             if(next!=null)
 79                 sb.append(",下一结点的值为:").append(next.value);
 80             else
 81                 sb.append(",当前结点为尾节点");
 82             if(sibling!=null)
 83                 sb.append(",指向任意结点的值为:").append(sibling.value);
 84             else
 85                 sb.append(",没有指向其他结点的任意结点");
 86             System.out.println(sb.toString());    
 87             node=node.next;
 88         }
 89     }
 90     public static void main(String[] args) {
 91         ComplexListNode node1=new ComplexListNode();
 92         ComplexListNode node2=new ComplexListNode();
 93         ComplexListNode node3=new ComplexListNode();
 94         ComplexListNode node4=new ComplexListNode();
 95         ComplexListNode node5=new ComplexListNode();
 96         node1.value=1;
 97         node1.next=node2;
 98         node1.sibling=node3;
 99         node2.value=2;
100         node2.next=node3;
101         node2.sibling=node5;
102         node3.value=3;
103         node3.next=node4;
104         node3.sibling=null;
105         node4.value=4;
106         node4.next=node5;
107         node4.sibling=node2;
108         node5.value=5;
109         node5.next=null;
110         node5.sibling=null;
111         printComplexList(node1);
112         System.out.println("=========================开始复制============================");
113         printComplexList(copyComplexList(node1));
114     }
115 }

[剑指offer] 复杂链表的复制

解法三:
寻找时空效率更高的解法。
第一步:复制链表,只是这个时候的复制,是把新的结点复制到原结点的后面,即N1->N1′->N2->N2’,这样m_pSibling指向的结点在新链表中也就是原结点的m_pNext结点
第二步:将第一步得到的链表拆分即可。

优化解法:上述方法的时间主要是用在了sibling节点的定位上,考虑优化此步骤。具体的做法是在复制节点的时候,把原节点N和复制出来的N’节点用一个map保存起来,这样在第二部连接sibling结点的时候就可以以O(1)的时间复杂度定位到相应的sibling节点,总体时间复杂度为O(n),空间复杂度也是O(n)

举例:1->2->3->4->5->null, from = 2, to =
4结果:1->4->3->2->5->null

请实现函数complexListNode* clone(complexListNode*
pHead),复制一个复杂链表。在复杂链表中,每个结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任意结点或者NULL.

在复杂链表中,每个结点除了有一个next指针指向下一个结点外,还有一个sibling指针指向链表中的任意结点或者nulL

题目描述:输出一个单链表的逆序反转后的链表。解题思路:用三个临时指针
prev、cur、next 在链表上循环一遍即可。

解法一:
先不管m_pSibling指针,将链表当做一个单链表复制,然后再遍历原链表,依次复制m_pSibling指针。但由于寻找新链表m_pSibling指针指向的结点需要遍历,因此时间复杂度为O(n^2)

题目:请实现一个函数,复制一个复杂链表。

[剑指offer] 从尾到头打印链表[剑指offer] 反转链表

struct complexListNode {
    int                                          m_nValue;
    complexListNode*                  m_pNext;
    complexListNode*                  m_pSibling;
};

第一步:根据原始链表的每个节点创建对应的复制结点,把复制结点连接在原结点的后面
第二步:设置复制出来的结点的任意结点sibling节点
第三步:把长链表拆分成两个链表

[剑指offer] 合并两个排序的链表

题目:

最优算法:

public class Solution { { public ListNode rotateRight(ListNode head, int k) { if  return null; int n = 1; ListNode cur = head; while  { ++n; cur = cur.next; } cur.next = head; int m = n - k % n; for (int i = 0; i < m; ++i) { cur = cur.next; } ListNode newhead = cur.next; cur.next = NULL; return newhead; }};

 

题目描述:删除单链表倒数第 n 个节点,1 <= n <=
length,尽量在一次遍历中完成。解题思路:双指针法,找到倒数第 n+1
个节点,将它的 next 指向倒数第 n-1个节点。

1.遍历链表,复制链表节点,并连接next节点。2.遍历链表,连接sibling节点。对于一个有n个节点的链表,由于定位每个节点的silbing节点都需要从链表的头结点开始经过O(n)步才能实现,因此这种方法的时间复杂度是O(n2)

题目描述:上面的问题是针对无环链表的,如果是链表有环呢?解题思路:如果两个有环单链表相交,那么它们一定共有一个环,即环上的任意一个节点都存在于两个链表上。因此可以先用之前快慢指针的方式找到两个链表中位于环内的两个节点,如果相交的话,两个节点在一个环内,那么移动其中一个节点,在一次循环内肯定可以与另外一个节点相遇。

题目描述:你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回和。解题思路:做个大循环,对每一位进行操作: