数据结构--单链表（实例）

数据结构--单链表（实例）

单链表例题

• 前言
• 1.得到倒数第K结点
• 2.单链表反转
• 3.单链表反转（使用栈实现，不改变原始链表的结构）
• 4.合并两个顺序链表

---

前言 1.得到倒数第K结点

代码如下（示例）：

// 查找链表的倒数第K个结点
    public void getKNode(int k){
        linkedNode temp = head.next;
        int size = getlinkedSize();
        int kNo = size - k + 1;
        boolean flag = false;
        if(temp.next == null){
            System.out.println("链表为空");
            return;
        }
        if(kNo == 0){
            System.out.println("该倒数第k结点是：" + head);
            return;
        }
        while (true){
            if(temp == null){
                break;
            }
            if(temp.no == kNo){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.println("该倒数第k节点是：" + temp);
        }else{
            System.out.println("没有找到");
        }
    }

2.单链表反转

（1）创建一个新的结点(reverseNode = new linkedNode())
（2）对添加的每一个结点进行遍历
（3）使用一个中间指针，每遍历到的结点都放到新节点的后面（reverseNode.next = cur）

代码如下（示例）：

// 单链表反转
    public void reverse(linkedNode head){
        if(head.next == null || head.next.next == null){
            return;
        }
        linkedNode cur = head.next;
        linkedNode next = null;
        linkedNode reverseHead = new linkedNode(0,"");
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

3.单链表反转（使用栈实现，不改变原始链表的结构）

代码如下（示例）：

// 从尾到头打印单链表
    public void showRravers(linkedNode head){
        Stack stack = new Stack<>();
        if(head.next == null){
            return;
        }
        linkedNode temp = head;
        while(true){
            if(temp.next == null){
                break;
            }
            stack.add(temp.next);
            temp = temp.next;
        }
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}

4.合并两个顺序链表

代码如下（示例）：

// 合并两个链表
    public linkNode mergeSort(linkNode head1, linkNode head2){
        linkNode p1 = head1;
        linkNode p2 = head2;

        if(head1.next.no < head2.next.no){
            head = head1;
            p1 = p1.next;
        }else{
            head = head2;
            p2 = p2.next;
        }

        linkNode p = head;
        while (p1 != null && p2 != null ){
            if(p1.no < p2.no){
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }else{
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        // 第二条链表空了
        if(p1 != null){
            p.next = p1;
        }
        //第一条链表空了
        if(p2 != null){
            p.next = p2;
        }
        return head;

    }