链表

发表于 | 分类于

链表经常拿来和数组进行比价，这里也讲一下链表和数组之间的区别。

  • 从内存的角度来看，数组开辟的空间地址必须是连续的，并且开辟完以后大小就固定了，而链表的话，限制条件很少，它开辟的空间，内存可以是不连续的，而且链表的长度可以增加。

  • 从对数据的处理角度来看，他们有各自擅长的领域

    例如查询一组数据中第i个位置的元素，用数组只需O(1)的时间复杂度，而使用链表需要O(n)的时间复杂度（链表必须逐个查询，直到查询到第i位），如果对一组数据进行插入或者删除操作，使用数组需要O(n)的时间复杂度（插入时，数组需要将要插入的位置空出来，该位置之后的元素，都需要后移，删除需要将空位补全，删除位置之后的元素，需要将其往前移动一位），而使用链表则无需移动的操作，所以插入和删除操作时间复杂度为O(1)。

通过几道链表相关的题目来增加对链表操作的熟练度

反转链表

题目：反转一个单链表。

详情请看LeetCode的206题

这道题相对简单，解题思路详看下图。

基于这个思路，基本可以写出解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode reverseList(ListNode head) {
    ListNode T = head;
    ListNode temp;
    if(head == null){
        return head;//防止传进来的是一个空的链表
    }
    while(T.next!=null){
        temp = T.next;//将要反转的节点存储起来
        T.next = temp.next;//将要反转的节点跳过
        temp.next = head;//将反转的节点插到头结点的前面
        head = temp;//使头节点依然指向第一个节点
    }
    return head;
}

反转链表二

题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

详情请看LeetCode的92题

这道题难点在于他不一定从头结点开始反转，所以要想解决这道题，需要先将这个问题解决。

此题的解题思路是基于上一题的思路，如有不明白之处请先看上面的解题过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public LinkList reverse(LinkList head,int m,int n){
    int i = 1;
    LinkList temp = head;
    LinkList pre;
    LinkList node;
    LinkList head_temp;
    while(i < m-1){
        temp = temp.next;
        i++;
    }
    pre = temp;
    if(m!=1){
        temp = temp.next;
        i++;
    }
    head_temp = temp;
    while(i<n){
        node = temp.next;
        temp.next = temp.next.next;
        node.next = head_temp;
        head_temp = node;
        i++;
    }
    if(m!=1){
        pre.next = head_temp;
        return head;
    }else{
        return head_temp;
    }
}