1.单链表常用操作

1.删除单链表中的指定节点

/**
 * 1.删除链表中指定节点
 *
 * @param header
 * @param node
 * @return
 */
public Node deleteNodeByNode(Node header, Node node) {
    if (node == null || header == null) {
        return header;
    }
    //删除节点为头节点的情况
    if (node == header) {
        header = null;
    }
    //删除节点为尾节点的情况
    else if (node.next == null) {
        Node temp = header;
        while (temp.next != node) {
            temp = temp.next;
        }
        temp.next = null;
    } else {//删除的节点为普通的节点
        node.data = node.next.data;
        node.next = node.next.next;
    }
    return header;
}

2.删除单链表中指定值的节点

(1). 利用栈删除单链表指定值的节点

/**
 * 2.1 利用栈删除单链表指定值的节点
 *
 * @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). 用普通查找的方式删除单链表中指定节点值的节点

/**
 * 2.2 用普通查找的方式删除单链表中指定节点值的节点
 *
 * @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;
    }
    pre.next = pre.next.next;
    return header;
}

3. 删除单链表中重复值的节点

/**
 * 3.删除单链表中重复的节点
 *
 * @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的数值
    int n1 = 0;
    //链表2的数值
    int n2 = 0;
    //n1+n2+ca的值
    int n = 0;
    //表示进位
    int ca = 0;
    //当前节点
    Node currentNode = null;
    //当前节点的前驱节点
    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.删除单链表中倒数第n个元素

/**
 * 6.删除单链表中倒数第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;
}