链表

• 1判断一个单链表是否有环
• 2判断一个单链表中环的入口
• 3在链表的第k个位置插入一个结点
• 4找到链表中的倒数第k个位置的结点
• 5链表逆置
• 6删除值为n的结点
• 7合并有序链表

---

• [1、判断一个单链表是否有环]
  可使用一快一慢两个指针，一个指针每次走一步，另一个指针一次走两步。若存在环，若干步后，快的指针会赶上慢的指针。否则则判定不存在环

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
static ListNode hasCircle(ListNode node) {
        if (node == null)
            return null;
        ListNode resultNode = null;
        ListNode slow = node.next;
        if (slow == null)
            return null;
        ListNode fast = slow.next;
        while (fast != null && slow != null) {
            if (fast == slow) {
                resultNode = fast;
                break;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        return resultNode ;
    }

• [2判断一个单链表中环的入口节点]
  首先使用1中方法判断链表中是否有环，获取环中任意一个节点，然后得到环的长度为n。
  然后定义两个指针，一个指针先走n步，然后两个指针在以相同的速度移动，当第二个指针走到入口节点时，第一个指针刚好走了一圈，也到达入口节点，这时就找到了环的入口节点。

static ListNode getEntryNode(ListNode node) {
        ListNode meetingNode = hasCircle(node);
        if (meetingNode == null)
            return null;
        int loopNum = 1;
        ListNode pNode1 = meetingNode;
        while (pNode1.next != meetingNode) {
            pNode1 = pNode1.next;
            ++loopNum;
        }
        pNode1 = node;
        for (int i = 0; i < loopNum; i++) {
            pNode1 = pNode1.next;
        }
        ListNode pNode2 = node;
        while (pNode1 != pNode2) {
            pNode1 = pNode1.next;
            pNode2 = pNode2.next;
        }
        return pNode1;
    }

• 3在链表的第k个位置插入一个结点
  若链表为空，则直接将插入数据作为第一个结点；
  若插入第一个位置和插入最后一个位置，都要考虑到。

      //返回头指针
    static ListNode insertNode(ListNode node, int k, int num) {
        ListNode kNode = new ListNode(num);
        if (node == null)
            node = new ListNode(num);
        int i = 0;
        ListNode preNode = node;
        while (preNode != null && i < k - 1) {
            if (++i == k - 1)
                break;
            preNode = preNode.next;
        }
        if ((k - 1) != i) {// 插入位置不合法
            return node;
        }
        if (k == 1) {// 插入首位
            kNode.next = node;
            node = kNode;
        } else {
            // 中间节点或尾结点
            kNode.next = preNode.next;
            preNode.next = kNode;
        }
        return node;
    }

• 4找到单链表中的倒数第k个位置的结点
  设链表长为n，从后往前查第k个结点即从前往后找的第n-k+1个结点。这时可以使用两个指针，第一个指针先走k-1步，第k步时，两个指针同时往前走，因为两个指针始终相差k-1，所以当第一个指针到达链表终点时，第二个指针刚好到达n-k+1个结点，即倒数第k个结点。

    static ListNode getKNode(ListNode node, int k) {
        ListNode pHead = node;
        ListNode pBehind = node;
        for (int i = 0; i < k - 1; i++) {
            pHead = pHead.next;
        }
        while (pHead.next != null) {
            pHead = pHead.next;
            pBehind = pBehind.next;
        }
        return pBehind;
    }

• 5链表逆置

public static ListNode reverseNode(ListNode node) {
        if (node == null)
            return null;
        ListNode reverseNode = null;
        ListNode head = node;
        ListNode preNode = null;
        while (head != null) {
            ListNode nextNode = head.next;
            if (nextNode == null)
                reverseNode = head;
            head.next = preNode;
            preNode = head;
            head = nextNode;
        }
        return reverseNode;
    }

• 6删除值为n的结点

public static ListNode delete(ListNode node, int data) {
        if (node == null)
            return null;
                //现将链表头部的值为data的数据删除
        while (node != null) {
            if (node.val == data)
                node = node.next;
            else   break;
        }
        ListNode preNode = null;//要删除的节点的前一个结点
        ListNode temp = node;//返回链表，先指向头结点
        ListNode head = node;//遍历指针
        while (head != null) {
            if (head.val != data) {
                preNode = head;
            } else {
                preNode.next = preNode.next.next;
            }
                        head = head.next;
        }
        return temp;
    }

• 7合并有序链表
  使用一个伪指针temp，构造新的链表node

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0) , temp = node;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next=l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        temp.next = (l1!=null)?l1:l2;   //若l1为null,则temp指向l2,否者指向l1
        return node.next;
    }
}