1.刪除單鏈表中的指定節(jié)點

/**
 * 1.刪除鏈表中指定節(jié)點
 *
 * @param header
 * @param node
 * @return
 */
public Node deleteNodeByNode(Node header, Node node) {
    if (node == null || header == null) {
        return header;
    }
    //刪除節(jié)點為頭節(jié)點的情況
    if (node == header) {
        header = null;
    }
    //刪除節(jié)點為尾節(jié)點的情況
    else if (node.next == null) {
        Node temp = header;
        while (temp.next != node) {
            temp = temp.next;
        }
        temp.next = null;
    } else {//刪除的節(jié)點為普通的節(jié)點
        node.data = node.next.data;
        node.next = node.next.next;
    }
    return header;
}

2.刪除單鏈表中指定值的節(jié)點

(1). 利用棧刪除單鏈表指定值的節(jié)點

/**
 * 2.1 利用棧刪除單鏈表指定值的節(jié)點
 *
 * @param header
 * @param value
 * @return
 */
public Node deleteNodeByValueFromStack(Node header, int value) {
    if (header == null) {
        return header;
    }
    Node temp = header;
    Stack<Node> stack = new Stack();
    while (temp.next != null) {
        if (temp.data != value) {
            stack.push(temp);
        }
        temp = temp.next;
    }
    while (!stack.isEmpty()) {
        stack.peek().next = header;
        header = stack.pop();
    }
    return header;
}

(2). 用普通查找的方式刪除單鏈表中指定節(jié)點值的節(jié)點

/**
 * 2.2 用普通查找的方式刪除單鏈表中指定節(jié)點值的節(jié)點
 *
 * @param header
 * @param value
 * @return
 */
public Node deleteNodeByValueFromFind(Node header, int value) {
    if (header == null) {
        return header;
    }
    Node pre = header;
    Node current = header.next;
    while (current != null) {
        if (current.data == value) {
            pre.next = current.next;
        } else {
            pre = current;
        }
        current = current.next;
    }
    return header;
}

3. 刪除單鏈表中重復值的節(jié)點

/**
 * 3.刪除單鏈表中重復的節(jié)點
 *
 * @param header
 */
public void deleteRepeatNodeFromHash(Node header) {
    if (header == null) {
        return;
    }
    HashSet<Integer> nodeHashSet = new HashSet<Integer>();
    Node pre = header;
    Node current = header.next;
    nodeHashSet.add(pre.data);
    while (current != null) {
        if (nodeHashSet.contains(current.data)) {
            pre.next = current.next;
        } else {
            nodeHashSet.add(current.data);
            pre = current;
        }
        current = current.next;
    }
}

4.兩個鏈表的值相加生成新的鏈表

/**
 * 4.兩個鏈表生成相加鏈表
 */
public Node addNode(Node head1, Node head2) {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    Node temp1 = head1;
    Node temp2 = head2;
    while (temp1 != null) {
        stack1.push(temp1.data);
        temp1 = temp1.next;
    }
    while (temp2 != null) {
        stack2.push(temp2.data);
        temp2 = temp2.next;
    }
    //鏈表1的數(shù)值
    int n1 = 0;
    //鏈表2的數(shù)值
    int n2 = 0;
    //n1+n2+ca的值
    int n = 0;
    //表示進位
    int ca = 0;
    //當前節(jié)點
    Node currentNode = null;
    //當前節(jié)點的前驅節(jié)點
    Node pnode = null;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        n1 = stack1.isEmpty() ? 0 : stack1.pop();
        n2 = stack2.isEmpty() ? 0 : stack2.pop();
        n=n1+n2+ca;
        currentNode=new Node(n%10);
        currentNode.next=pnode;
        pnode=currentNode;
        ca=n/10;
    }
    if (ca==1)
    {
        pnode=currentNode;
        currentNode=new Node(n/10);
        currentNode.next=pnode;
    }
    return currentNode;
}

5.判斷單鏈表是否為回文結構

/**
 * 5.判斷單鏈表是否為回文結構
 * 比如1 2 3 4 5 4 3 2 1(正著閱讀和倒著順序一樣)
 */
public boolean isPalindrome(Node head)
{
    if (head==null)
    {
        return false;
    }
    Stack<Node> nodes=new Stack<Node>();
    Node current=head;
    while (current!=null)
    {
        nodes.push(current);
        current=current.next;
    }
    Node temp=head;
    while (temp.next!=null)
    {
        if (temp.data!=nodes.pop().data)
        {
            return false;
        }
        temp=temp.next;
    }
    return true;
}

6.刪除單鏈表中倒數(shù)第n個元素

/**
 * 6.刪除單鏈表中倒數(shù)第n個元素
 *
 * @param head
 * @param k
 * @return
 */
public Node removelastKthNode(Node head, int k) {
    if (k <= 0 || head == null) {
        return head;
    }
    Node p = head;
    for (int i = 0; i < k; i++) {
        if (p.next != null) {
            p = p.next;
        } else {
                return head;
        }
    }
    Node q=head;
    while (p.next!=null)
    {
        p=p.next;
        q=q.next;
    }
    q.next=q.next.next;
    return head;
}

7.反轉鏈表

/**
 * 7.反轉鏈表
 *
 * @param header
 */
public void reserve(Node header) {
    if (header == null) {
        return;
    }
    Node pCurrent = header.next;
    Node pPre = null;
    Node pNext = null;
    while (pCurrent != null) {
        pNext = pCurrent.next;
        pCurrent.next = pPre;
        pPre = pCurrent;
        pCurrent = pNext;
    }
    header.next = pCurrent;
}