算法原理和实践(C++)

发表于 | 分类于

Reorder List

Given a linked list and a value x, write a function to reorder this list such that all nodes less than x come before the nodes greater than or equal to x.
可以使用dummy node来减少判断header是否为空的边界条件。

代码：class2/reorder_list.c

ListNode *reorderList(ListNode *head, int x) {        
    ListNode *newHead = NULL;
    ListNode *aDummy = new ListNode(0);
    ListNode *aCurr = aDummy;
    ListNode *bDummy = new ListNode(0);
    ListNode *bCurr = bDummy;

    while(head) {       
        ListNode *next = head->next;
        head->next = NULL;        
        if( head->val < x ) {
            aCurr->next = head;
            aCurr = head;
        } else {
            bCurr->next = head;
            bCurr = head;
        }         
        head = next;
    }      

    aCurr->next = bDummy->next;
    newHead  = aDummy->next;

    delete aDummy;
    delete bDummy;

    return newHead;
}

链表的基本技巧

  1. 链表的插入
  2. 链表的删除
  3. 链表逆序（微软特别喜欢考）
  4. 合并链表
  5. 找到链表的中间项

Sort List

Sort a linked list in O(n log n) time using contant space complexity.
Hint: merge sort
问题: log n的算法复杂度是怎么得到的。

//里面有两个指针，一个快一个慢，当快的指针到达终点的时候，慢的指针刚好到达终点
public class Solution {            
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }    
    //将两个链表按从小到大排序生成一个新的链表
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if (head1 != null) {
            tail.next = head1;
        } else {
            tail.next = head2;
        }

        return dummy.next;
    }

    public ListNode sortList(ListNode head) {
        //先检查head值是否为空
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = findMiddle(head);

        ListNode right = sortList(mid.next);
        mid.next = null;//把链表彻底断开成两截
        ListNode left = sortList(head);

        return merge(left, right);
    }
}

Two Pointers

Linked List Cycle I, II

Given a linked list, determine if it has a cycle in it.
如何判断一个单链表中有没有环?
可以开辟一个hashmap,记录每一个访问过的node.但是需要开辟整个linked list的空间。
Follow up: Can you solve it without using extra space
可以先设定一个快指针，每次走两步，慢指针走一步，如果链表中有环,快指针肯定能够和慢指针相遇。
Return the node where the cycle begins, if there is no cycle, return null.找到环的第一个节点
慢者: a+b
快者: a+b+n(c+b)
关系: a+b+c+b = 2(a+b) => a=c
一般而言，如果环特别小，我们就能得到:a=nc+(n-1)b = c + (n-1)(b+c) 这样的结论,可以令c’=c+(n-1)(b+c),则a=c’,算法并没有发生什么改变。

public static ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
}

while (true) {
    if (fast == null || fast.next == null) {
        return null; //遇到了null，说明不存在环
    }
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) {
        break;//第一次相遇在Z点
    }
    slow = head; //slow从头开始走
    while (slow != fast) { //两者相遇在Y点，则推出
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Remove/Find Nth Node From End of List

先让一个指针先跑n步，再让两个指针同时跑 下面的代码是说如何拿到倒数第k个元素

ListNode *findkthtoLast(ListNode *head,int k){
    ListNode *runner = head;
    ListNode *chaser = head;

    if (head == NULL || k < 0)
    return NULL;

    for(int i = 0; i < k; i++)
        runner = runner->next;

    if( runner == NULL )
        return NULL;

    while( runner->next != NULL ) {
        chaser = chaser->next;
        runner = runner->next;
    }
    return chaser;
}

Find the Middle of Linked List

代码如下:

ListNode *midpoint( ListNode *head) {
    ListNode *chaser = head, *runner = head;
    if (head == NULL)
        return NULL;

    while (runner->next && runner->next->next ) {
        chaser = chaser->next;
        runner = runner->next->next;
    }
    return chaser;
}

判断两个单链表是否有交点

如果一个有环一个没有环，则肯定不相交 如果两个都没有环，判断两个列表的尾部是否相等 如果两个都有环，判断一个链表上的Z点是否在另一个链表上

如何找到第一个相交的节点

求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算） 假设L1<L2, 用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)，然后两个一起走，直到两者相遇。

Reverse Linked List反转链表

ListNode *reverseLinkedList( ListNode *head ) {
    ListNode *prev = NULL;
    ListNode *next = head->next;
    while(head) {
        head->next = prev;
        prev = head;
        head = next;
        next = next->next;
    }
    return prev;
}

Merge K Sorted Lists

Leetcode题目链接
从2个扩展到k个，对k个东西进行排序要想到堆的概念。

public class Solution {
    private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
        public int compare(ListNode left, ListNode right) {
            if (left == null) {
                return 1;
            } else if (right == null) {
                return -1;
            }
            return left.val - right.val;
        }
    };

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }

        Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.add(lists.get(i));
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            tail.next = head;
            tail = head;
            if (head.next != null) {
                heap.add(head.next);
            }
        }
        return dummy.next;
    }
}

Copy List with Random Pointer

Leetcode题目链接
是linked list里面比较难的题目 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. 可以用hashmap来做也可以不用。 首先是是hashmap版本的算法。

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode pre = dummy, newNode;
        while (head != null) {
            if (map.containsKey(head)) {
                newNode = map.get(head);
            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            }
            pre.next = newNode;

            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    newNode.random = map.get(head.random);
                } else {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                }
            }

            pre = newNode;
            head = head.next;
        }

        return dummy.next;
    }
}

不使用hashmap的算法。 original指针的结构如下:

  • next指针:1->2->3->4->5
  • random指针:1->3->5->2->1

算法步骤:

  1. 复制original list的next指针到copy list，并把original list的next指针指向对应的copy list的节点下。
  2. 将original_node[i].random.next赋给original_node[i].next.random，完成copy list的random指针的赋值
  3. 将两个链表的关系断开。
//No HashMap version
public class Solution {
    private void copyNext(RandomListNode head) {
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random;
            newNode.next = head.next;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.next.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            head = head.next;
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
        }
        return newHead;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }
}
打赏还是要有的，万一有人打赏呢！