[数据结构与算法]NO.4 剑指Offer

剑指Offer第4天刷题

今天开始复习链表：

翻转链表

需要保留一个节点的前驱和后继，用cur来遍历节点，head就是它的前驱，curNext是它的后继

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode curNext = cur.next;
        cur.next = null;
        cur = curNext;
        while(cur != null){
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

合并两个排序的链表

定义一个傀儡节点，让两个链表依次比较，头最小的作为它的后继，遍历两个链表，最后一个链表遍历完成之后，将另一个链表剩下的部分直接放过来最后返回傀儡节点的下一个节点就是新链表的头结点。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 != null) cur.next = list1;
        if(list2 != null) cur.next = list2;
        return newHead.next;
    }
}

删除链表中重复的结点

定义一个傀儡节点，让链表从头结点（cur）就开始与后一个(cur.next)比较，保留它的前驱prev，如果相同，就让cur一直往后走，直到不相同为止，然后将新的cur作为prev的后继，最后将链表的最后一个节点的next设置为null，防止有最后一个节点也是重复的。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode newHead = new ListNode(-1);
        ListNode prev = newHead;
        ListNode cur = pHead;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }else{
                prev.next = cur;
                prev = prev.next;
                cur = cur.next;
            }
        }
        prev.next = null;
        return newHead.next;
    }
}