链表题目

5. 从尾到头打印链表

思路：利用栈实现

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }
}

---

15. 链表中倒数第k个结点

思路：两个指针，一个先走K步，之后两指针同时移动，直到相等

public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k<=0)
            return null;
        
        ListNode fast = head;
        ListNode slow = head;
        
        for(int i=0;i<k-1;i++){
            fast = fast.next;
            if(fast == null)
                return null;
        }
        
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

---

16.反转链表

public ListNode ReverseList(ListNode head) {
        if(head == null)
            return null;
        ListNode pre = null;
        ListNode next = null;

        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

---

17. 合并两个排序链表

public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null )
            return list2;
        if(list2 == null)
            return list1;
        
        ListNode p = new ListNode(-1);
        
        if(list1.val > list2.val){
            p = list2;
            p.next = Merge(list1,list2.next);
        }else{
            p = list1;
            p.next = Merge(list1.next,list2);
        }
        
        return p;
    }

---

26. 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

1. 复制节点

   
   

2. 复制指针

   
   

3. 拆分

   
   

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    // 复制节点
    public void CloneNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        
        while(pNode!=null){
            RandomListNode pCloned = new RandomListNode(pNode.label);
            pCloned.next = pNode.next;
            pCloned.random = null;
            
            pNode.next = pCloned;
            
            pNode = pCloned.next;
        }
    }
    // 复制指针
    void ConnectSibingNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        while(pNode!=null){
            RandomListNode pCloned = pNode.next;
            if(pNode.random !=null)
                pCloned.random = pNode.random.next;
            pNode = pCloned.next;
        }
    }

    // 拆分
    RandomListNode RonnectNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        RandomListNode pClonedHead = null;
        RandomListNode pClonedNode = null;
        
        if(pNode!=null){
            pClonedHead = pClonedNode = pNode.next;
            pNode.next = pClonedNode.next;
            pNode = pNode.next;
        }
        while(pNode!=null){
            pClonedNode.next = pNode.next;
            pClonedNode = pClonedNode.next;
            pNode.next = pClonedNode.next;
            pNode = pNode.next;
        }
        
        return pClonedHead;
    }
    public RandomListNode Clone(RandomListNode pHead)
    {
        CloneNodes(pHead);
        ConnectSibingNodes(pHead);
        return RonnectNodes(pHead);
    }
}

---

56. 链表中环的入口节点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路

1. 设置两个指针，一个是快指针fast，一个是慢指针slow，fast一次走两步，slow一次走一步，如果单链表有环那么当两个指针相遇时一定在环内。
2. 此时将一个指针指到链表头部，另一个不变，二者同时每次向前移一格,当两个指针再次相遇时即为环的入口节点。如果fast走到null则无环。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead.next == null || pHead.next.next == null)
            return null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        while(fast != null){
            if(fast == slow){
                fast = pHead;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return null;
    }
}

---

57. 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路

1. 首先添加一个头节点pHead （以方便碰到第一个，第二个节点就相同的情况）
2. 设置 first ，second 指针，first从头开始，second 在 first下一位
3. 如果发现second节点和next不相等，两个节点继续移动
4. 如果发现second节点和next相等，则first不动，second继续移动，直到移动到最后一个不重复数字，删除重复节点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return pHead;
        ListNode head = new ListNode(-1);
        head.next = pHead;
        ListNode first = head;
        ListNode second = first.next;
        while(second != null){
            if(second.next != null && second.val == second.next.val){
                while(second.next != null && second.val == second.next.val){
                    // 删除重复节点
                    second = second.next;
                }
                first.next = second.next;
            }else{
                first = first.next;
            }
            second = second.next;
        }
        return head.next;
    }
}