【代码随想录】学习链表

跟着卡哥学习

学习记录

• 5月24日

链表类型：单链表、双链表、循环链表

• C语言

typedef struct {
    int val;
    struct MyLinkedList* next;
}MyLinkedList;

• C++语言

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

• Java语言
  定义类结构作为一个node

// 单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
//双链表
class MyLinkedList {
    class ListNode {
        int val;
        ListNode next,prev;
        ListNode(int x) {val = x;}
    }

• Go语言

type Node struct {
	Val  int
	Next *Node
	Pre  *Node
}

public int get(int index);      // 根据下表索引获取元素
public void addAtHead(int val); // 在头部添加node
public void addAtTail(int val); // 在尾部添加node
public void addAtIndex(int index, int val); // 指定位置插入
public void deleteAtIndex(int index);       // 指定位置删除

主要是写Java的代码

定义接口

public interface List{
	public int get(int index);      // 根据下表索引获取元素
	public void addAtHead(int val); // 在头部添加node
	public void addAtTail(int val); // 在尾部添加node
	public void addAtIndex(int index, int val); // 指定位置插入
	public void deleteAtIndex(int index);       // 指定位置删除
}

• 移除链表元素
• 反转链表 lc206
• 两两交换链表中的节点
• 删除链表的倒数第N个节点
• 链表相交
• 环形链表

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1-

public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        // new 一个head
        ListNode dummpyNode = new ListNode();
        ListNode p = head, q = null;
        //头插法
        while(p != null){
            q = p.next;
            p.next = dummpyNode.next;
            dummpyNode.next = p;
            p = q;
        }
        return dummpyNode.next;
    }

递归方法

public ListNode reverseList(ListNode head) {
        
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next= null;
        return p;
}

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode p = dummyNode;
		// 这个模拟的思路，自己一直搞来搞去，搞得没弄明白，像他这样写清楚， 没有NPE
        while(p.next != null && p.next.next != null){
            ListNode tmp = head.next.next;
            p.next = head.next;
            head.next.next = head;
            head.next = tmp;
            p = head;
            head = head.next;
        }
        return dummyNode.next;
    }

//TODO 存在NPEbug需要修复
  public ListNode swapPairs(ListNode head) {
        ListNode r = head, p = head.next;
        if(p.next == null){
            //只有2个节点
            p.next = r;
            r.next = null;
            return p;
        }
        ListNode q = p.next;
        while(q != null){
            p = p.next;
            q = q.next.next;
        }
        //p到了链表中点
        ListNode nextHead = p.next;
        p.next = null;
        ListNode left = swapPairs(r);
        ListNode right = swapPairs(nextHead);
        left.next = right;
        return head;
    }

• 代码随想录-链表