Leetcode

206. 反转链表

递归方法

class Solution { public ListNode reverseList(ListNode head) { //递归终止条件是当前为空，或者下一个节点为空 if(head==null || head.next==null) { return head; } //这里的cur就是最后一个节点 ListNode cur = reverseList(head.next); //如果链表是 1->2->3->4->5，那么此时的cur就是5 //而head是4，head的下一个是5，下下一个是空 //所以head.next.next 就是5->4 head.next.next = head; //防止链表循环，需要将head.next设置为空 head.next = null; //每层递归函数都返回cur，也就是最后一个节点 return cur; } }

迭代方法（思路可参考这里）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while(curr!=null) { ListNode nexttemp =curr.next; curr.next= prev; prev=curr; curr=nexttemp; } return prev; } }

876. 链表的中间结点

思路：快慢指针的应用

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode slow =head; while(fast!=null&&fast.next!=null) { fast=fast.next.next; slow=slow.next; } return slow; } }

143. 重排链表

思路：由上面两道题的铺垫，这道题就是找到链表中点，分成两部分，将后半部分链表逆转，插空插入前一部分链表中，实现链表逆转

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode mid = middleNode(head); ListNode l1 = head; ListNode l2 = mid.next; mid.next = null; l2 = reverseList(l2); mergeList(l1, l2); } public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_tmp; ListNode l2_tmp; while (l1 != null && l2 != null) { l1_tmp = l1.next; l2_tmp = l2.next; l1.next = l2; l1 = l1_tmp; l2.next = l1; l2 = l2_tmp; } } }