Document

链表的习题

  1. 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来的两个链表的存储空间，不另外占用其他的存储空间，表中不允许有重复的数据。
    为了方便不处理边界采用带哨兵的单链表形式
    LIST-ORDERLY-MARGE(L1,L2)
    1 p1=L1.nil.next
    2 p2=L2.nil.next
    //new tail=L.nil
    3 while p1!=L1.nil and p2!=L2.nil
    4 if p1.key<= p2.key < view>
    5 if p1.key!=tail.key
    6 temp=p1.next
    7 p1.next=tail.next
    8 tail.next=p1
    9 tail=tail.next
    10 p1=temp
    11 else
    12 p1=p1.next
    13 else
    14 if p2.key!=tail.key
    15 temp=p2.next
    16 p2.next=tail.next
    17 tail.next=p2
    18 tail=tail.next
    19 p2=temp
    20 else
    21 p2=p2.next
    22 while p1!=L1.nil
    23 if p1.key!=tail.key
    24 temp=p1.next
    25 p1.next=tail.next
    26 tail.next=p1
    27 tail=tail.next
    28 p1=temp
    29 else
    30 p1=p1.next
    31 while p2!=L2.nil
    32 if p2.key!=tail.key
    33 temp=p2.next
    34 p2.next=tail.next
    35 tail.next=p2
    36 tail=tail.next
    37 p2=temp
    38 else
    39 p2=p2.next
    • 根据题目描述，链表L1,L2是递增的，因此容易想到使用双指针p1和p2遍历两链表链表，根据L1.key和L2.key的大小关系确定添加结点顺序，两指针交替前进，直至遍历完毕
    • 引入哨兵nil:由于初始状态合并链表中无结点，因此循环第一轮无法将结点添加到合并链表L中(边界问题),故初始化一个哨兵nil(哨兵请看List1-1)
    • 为了方便在表尾添加数据，增加一个tail指针指向合并表L的表尾，由于开始无结点，故指向L.nil(哨兵).
    算法流程：
    初始化：哨兵L.nil,表尾tail=L.nil
    循环合并：(在更新时候，此题注意边界查看表尾tail.key是否与添加的key相等)
    1. 当p1.key<=p2.key时，表尾tail.next指向p1,更新tail和p1< li>
    2. 当p2.key< p1.key时，表尾tail.next指向p2,更新tail和p2
    合并剩余尾部：跳出时有两种情况，即L1遍历完或L2遍历完
    时间复杂度为：Ο(n+m)
    剑指 Offer 25合并两个排序的链表
  2. 将两个非递减的有序链表合并为一个非递增的有序链表，要求结果链表仍使用原来的存储空间，允许有重复。与上题一样为了更容易处理边界采用哨兵且要求空间复杂度改为Ο(1)
    LIST-Turn-ORDERLY-MARGE(L1,L2)
    1 new L3.nil
    2 p1=L1.nil.next
    3 p2=L2.nil.next
    4 while p1!=L1.nil and p2!=L2.nil.next
    5 if(p1.key<=p2.key>)
    6 temp=p1.next
    7 p1.next=L3.nil.next
    8 L3.nil.next=p1
    9 p1=temp
    10 if(p2.key< p1.key)
    11 temp=p2.next
    12 p2.next=L3.nil.next
    13 L3.nil.next=p2
    14 p2=temp
    15 while p1!=L1.nil
    16 temp=p1.next
    17 p1.next=L3.nil.next
    18 L3.nil.next=p1
    19 p1=temp
    20 while p2!=L2.nil
    21 temp=p2.next
    22 p2.next=L3.nil.next
    23 L3.nil.next=p2
    24 p2=temp
    算法流程：
    初始化：哨兵L3.nil
    循环合并：(在使用头插法进行插入时记得保留待插入结点的next指针，不然会破坏链表的结构)
    1. 当p1.key<=p2.key时，在L3.nil与L3.nil.next(上一个较小的元素)之间插入p1< li>
    2. 当p2.key< p1.key时，在L3.nil与L3.nil.next(上一个较小的元素)之间插入p2
    合并剩余尾部：跳出时有两种情况，即L1遍历完或L2遍历完。
    1 L1没有遍历完，继续进行遍历进行头插.
    2 L2没有遍历完，继续进行遍历进行头插.
    最后得到一个非递增的有序链表(也就是递减的链表)