链表的结构

链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

打题时最常见的链表结构如下
非循环单向链表

交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值哦,而是需要实际的进行节点交换。
1.递归方法

/**
 * 链表结点定义
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 
class Solution {
    public ListNode swapPairs(ListNode head) {
        if ((head == null) || (head.next == null)) {
            return head;  //递归退出
        }
        ListNode first=head,second=head.next;

        first.next = swapPairs(second.next); //递归从末尾开始逆转
        second.next = first;  //将目前第二结点的next指向第一结点,从而实现交换。
        return second;
    }
}

2.非递归

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode now=head,next, newHead = pre;
        while(now != null && now.next != null){
            next = now.next;

            pre.next = next;
            now.next = next.next;
            next.next = now;

            pre = now;
            now = now.next;
        }
        return newHead.next;
    }
}

原地链表逆转

给定一个链表的头指针,要求只遍历一次,将单链表中的元素的顺序翻转过来。
要求不创建新的空间。

node *reverseList(node *H){
    if (H->next == nullptr) //链表为空或者仅1个数直接返回
        return H;
    node *p = H, *newH = nullptr;
    while (p != nullptr)                 //一直迭代到链尾
    {
        node *tmp = p->next;          //暂存p下一个地址,防止变化指针指向后找不到后续的数
        p->next = newH;               //p.next指向前一个空间
        newH = p;                     //新链表的头移动到p,扩长一步链表
        p = tmp;                   //p指向原始链表p指向的下一个空间
    }
    return newH;
}


Last modification:April 4th, 2020 at 09:19 pm
If you think my article is useful to you, please feel free to appreciate