链表专题

记录一下《剑指offer》上关于链表的题目

1.  在O（1）时间内删除链表的节点  #13
2. 链表中倒数第k个节点　　#15
3. 翻转链表　　  #16
4. 合并2个排序链表  #17
5. 复杂链表的复制  # 26
6. BST与双向链表  # 27
7. 两个链表的第一个公共节点 # 37

__________________________________

3. 翻转链表：

   需要三个指针，一个 prevcurrent ext， 总共分为3步

   首先，需要保存next_temp, if next == null ，即说明到达尾节点了，该尾节点就是翻转链表后的头节点。

   然后 设置 cur.next = prev;

   然后，向后移动 prev = cur; cur = next_temp(事先保存的下一个节点)

   代码：

 public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode prev = null;
        ListNode reverseHead = null;
        while(cur != null){
            ListNode next_temp = cur.next;
            if(next_temp == null){
                reverseHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = next_temp;
        }
        return reverseHead;
    }

　　测试用例：

• 输入的链表头指针为空。
• 输入的链表只有一个节点。
• 输入的链表有多个节点。

 ____________________________

4. 合并两个排序链表

如果一个链表为空，返回另一个即可。（这个操作，可以有效解决两个空链表的情况）

 然后，在确定合并之后链表的头节点，即两个两个头节点中较小的那一个。

之后就可以用递归的方式了，递归基 为红色情况。如此即可。

代码：红色的操作很漂亮，代码简洁

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        ListNode head;
        if(l1.val < l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }else{
            head = l2;
            head.next = mergeTwoLists(l1,l2.next);
        }
        return head;
    }

　　

特例

• 功能测试：输入的两个链表有多个节点；节点的值互不相同，或者存在值相等的多个节点。
• 特殊测试：两个链表中一个或者两个的链表头为空；两个链表中只有一个节点。