关于链表的心得体会

1.反转链表

　　经典考题，针对链表的反转，第⼀时间需要联想到将链表的指针进⾏反转，⽽这种⼀系列的变化，可以使⽤递归，也可以使⽤while迭代

假设链表为 1 \\rightarrow 2 \\rightarrow 3 \\rightarrow \\varnothing1→2→3→∅，我们想要把它改成 \\varnothing \\leftarrow 1 \\leftarrow 2 \\leftarrow3∅←1←2←3。

在遍历链表时，将当前节点的 \extit{next}next 指针改为指向前⼀个节点。由于节点没有引⽤其前⼀个节点，因此必须事先存储其前⼀个节点。在更改引⽤之前，还需要存储后⼀个节点。最后返回新的头引⽤。

class Solution {

public ListNode reverseList(ListNode head) { //使⽤指针的⽅法对全部的值进⾏反转 //⾸先定义空的节点 ListNode pre = null; ListNode cur = head; while(cur!=null){

ListNode next = cur.next;

//当前节点的⼦节点将指向前节点 cur.next = pre;

//当前节点变为前节点 pre = cur;

//下⼀个节点变为当前节点 cur = next; }

return pre;}}

递归

递归版本稍微复杂⼀些，其关键在于反向⼯作。假设链表的其余部分已经被反转，现在应该如何反转它前⾯的部分？假设链表为：

n1→…→nk−1→nk→nk+1→…→nm→∅

若从节点 n_{k+1}nk+1 到 n_mnm 已经被反转，⽽我们正处于 n_knk。n1→…→nk−1→nk→nk+1←…←nm

我们希望 n_{k+1}nk+1 的下⼀个节点指向 n_knk。

所以，n_k.\extit{next}.\extit{next} = n_knk.next.next=nk。

需要注意的是 n_1n1 的下⼀个节点必须指向 \\varnothing∅。如果忽略了这⼀点，链表中可能会产⽣环

class Solution {

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

　　ListNode newHead = reverseList(head.next);　　head.next.next = head;　　head.next = null;　　return newHead;　　}}

2.链表取中间节点

给定⼀个头结点为 head 的⾮空单链表，返回链表的中间结点。如果有两个中间结点，则返回第⼆个中间结点。⽰例 1：输⼊：[1,2,3,4,5]

输出：此列表中的结点 3 (序列化形式：[3,4,5])

返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了⼀个 ListNode 类型的对象 ans，这样：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.⽰例 2：

输⼊：[1,2,3,4,5,6]

输出：此列表中的结点 4 (序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第⼆个结点。

需要联想到的⽅法：

1.双指针（快慢指针）法，既然是⼀个数组，我分别定义⼀个⾛两步的head和⼀个⾛⼀步的head，每当head1⾛两步，我的head2⾛1步，head1⾛完，head2刚好⾛到中间。

public ListNode middleNode(ListNode head) {　　ListNode slow = head, fast = head;　　while (fast != null && fast.next != null) {　　slow = slow.next;　　fast = fast.next.next;　　}

　　return slow;}

2.单指针法：我每⾛⼀步，i++,在第⼆次遍历是，我⾛到i/2步，结束

public ListNode middleNode(ListNode head) {　　int n = 0;

　　ListNode cur = head;　　while (cur != null) {　　++n;

　　cur = cur.next;}

int k = 0;cur = head;

while (k < n / 2) {++k;

cur = cur.next;}

return cur;}

3.数组法：将节点变为数组，并记录⼀个i++，变成节点数组之后直接获取最⼤i/2的数组内容，也就是中间的结点。

public ListNode middleNode(ListNode head) {ListNode[] A = new ListNode[100];int t = 0;

while (head != null) {A[t++] = head;head = head.next;}

return A[t / 2];}

3.合并两个有序链表

将两个升序链表合并为⼀个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输⼊：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]⽰例 2：

输⼊：l1 = [], l2 = []输出：[]⽰例 3：

输⼊：l1 = [], l2 = [0]输出：[0]

递归，思想是这样的，我先将l1和l2看作⼀个单独的结点，进⾏判断，如果L1⼩于L2，我就讲L1.next和L2的剩余内容⼜看作⼀个整体，再进⾏递归。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2;

}else if(l2 == null){ return l1;

}else if(l1.vall1.next = mergeTwoLists(l1.next,l2); return l1; }else{

l2.next = mergeTwoLists(l1,l2.next); return l2; } }

4.将链表两两进⾏反转

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

输⼊：head = [1,2,3,4]输出：[2,1,4,3]

递归，将前两个看作⼀个单位进⾏递归，返回

public ListNode swapPairs(ListNode head) {

if(head==null||head.next==null){return head;}

ListNode pre = head; ListNode cur = pre.next; ListNode next = cur.next; pre.next = swapPairs(next); cur.next = pre; return cur; }

5.将链表回⽂变成数组和递归⽅法1.变成数组

class Solution {

public boolean isPalindrome(ListNode head) {List vals = new ArrayList();// 将链表的值复制到数组中ListNode currentNode = head;while (currentNode != null) {vals.add(currentNode.val);

currentNode = currentNode.next;}

// 使⽤双指针判断是否回⽂int front = 0;

int back = vals.size() - 1;while (front < back) {

if (!vals.get(front).equals(vals.get(back))) {return false;}

front++;back--;}

return true;}}

2.递归

class Solution {

private ListNode frontPointer;

private boolean recursivelyCheck(ListNode currentNode) {if (currentNode != null) {

if (!recursivelyCheck(currentNode.next)) {return false;}

if (currentNode.val != frontPointer.val) {return false;}

frontPointer = frontPointer.next;}

return true;}

public boolean isPalindrome(ListNode head) {frontPointer = head;

return recursivelyCheck(head);}}