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

剑指Offer第六天

复杂链表的复制

在这里使用哈希表来保存新旧节点的对应关系，然后在哈希表中更新next和random字段

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while(cur != null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

从尾到头打印链表

• 将链表反转之后，遍历节点，正序输出
• 用 ArrayLis t中 add 方法将值插入到指定的位置，遍历节点时，将节点的值都插入到 list 的 0 位置

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = listNode;
        while(cur != null){
            list.add(0,cur.val);
            cur = cur.next;
        }
        return list;
    }
}

判断链表是否为回文结构

将链表从中间节点到尾节点进行翻转，然后从两头分别遍历，判断是否值相等(其中当链表是偶数个节点那么就要判断 head.next 和 slow 是否相等)。

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null || head.next == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            if(head.next.val == slow.val){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}