复习系列1-DS单链表--结点交换

DS单链表--结点交换

这题简单粗暴，利用上一题的类实现，直接更换数据值。（当然这是取巧的办法，如果两个结点含的数据很多，还是用这种办法就显得臃肿笨重，交换做法如下：

对于要交换的结点 n1 和 n2 ，找到其前一个结点 s1 和 s2：【此处交换了n1和n2的前驱】

t = s1->next; （指向 n1）                    【交换后继】  t = s1->next->next;（指向n1->next）

s1->next = s2->next; （s1 指向 n2）                          s1->next->next = s2->next->next;（n1->next 指向 n2->next ）

s2->next = t; （s2 指向 n1）                                       s2->next->next = t;（n2->next 指向 n1->next）

题目描述

用C++实现含头结点的单链表，然后实现单链表的两个结点交换位置。

注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换

交换函数定义可以参考：

swap（int  pa, int pb)  //pa和pb表示两个结点在单链表的位置序号

swap (ListNode * p, ListNode * q)  //p和q表示指向两个结点的指针

输入

第1行先输入n表示有n个数据，接着输入n个数据

第2行输入要交换的两个结点位置

第3行输入要交换的两个结点位置

输出

第一行输出单链表创建后的所有数据，数据之间用空格隔开

第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开

第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开

如果发现输入位置不合法，输出字符串error，不必输出单链表

样例输入

5 11 22 33 44 55

1 4

2 6

样例输出

11 22 33 44 55

44 22 33 11 55

error

提示

注意要用链表实现哦！

Solution：

import java.util.*;
/**
 * @author: Liu Canbin
 * @date: 2019/1/2
 */

public class Main {
//    private static List<Integer> list = new ArrayList<Integer>();
    private static List list = new List();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // init data
        int n = scanner.nextInt();
        for (int i = 0; i <n ; i++) {
            list.add(scanner.nextInt());
        }
        show();
        //swap
        for (int i = 0; i <2 ; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (a<1 || a> list.size()-1){
                System.out.println("error");
            }else if (b<1 || b>list.size()-1){
                System.out.println("error");
            }else {
                list.swap(a,b);
                show();
            }
        }
    }

    private static void show(){
        for (int i = 1; i <list.size() ; i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
    }
}

class List{
    Node head;

    List(){
        head = new Node(0);
    }
    void add(int data){
        Node node = new Node(data);
        Node temp = head;
        while (temp.next!=null){
            temp = temp.next;
        }
        temp.next =node;
    }
   
    void swap(int a,int b){
        //简单粗暴，直接找到对应的值，并更换
        int temp = find(b).data;
        find(b).data =find(a).data;
        find(a).data = temp;
    }
  
    int get(int index){
        Node temp = head;
        for (int i = 1; i <index ; i++) {
            temp = temp.next;
        }
        return temp.next.data;
    }
    Node find(int index){
        Node temp = head;
        for (int i = 1; i <index ; i++) {
            temp = temp.next;
        }
        return temp.next;
    }

    int size(){
        int sum =0;
        Node temp = head;
        while (temp!=null){
            sum++;
            temp = temp.next;
        }
        return sum;
    }
}

class Node{
    int data;
    Node next;
    public Node(int data){
        this.data =data;
        next = null;
    }
}