1、反转链表
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
1. 示例1 2. 输入： 3. {1,2,3} 4. 返回值： 5. {3,2,1} 6. 7. 8. 9. 示例2 10. 输入： 11. {} 12. 返回值： 13. {} 14. 说明： 15. 空链表则输出空
思路描述：为了反转链表，简单一点说就是把结点的next值进行一个修改，如果我们用cur来记录当前的结点，那么在修改指向的时候，我们需要知道它的前一个结点(pre)和后一个结点(curNext)，因为一旦指向修改完成后，后面的结点就找不到了，所以我们需要记录一下。所以我们首先记录一下当前结点的下一个结点，然后把当前结点cur的next指向pre,让pre后移，也就是pre=cur；然后让cur指向记录的curNext即可，直至遍历完整个链表。
AC代码：
1. /* 2. public class ListNode { 3. int val; 4. ListNode next = null; 5. 6. ListNode(int val) { 7. this.val = val; 8. } 9. }*/ 10. public class Solution { 11. public ListNode ReverseList(ListNode head) { 12. 13. ListNode cur=head; 14. 15. ListNode pre=null; 16. 17. while(cur!=null){ 18. ListNode curNext=cur.next; 19. cur.next=pre; 20. pre=cur; 21. cur=curNext; 22. } 23. 24. return pre; 25. 26. } 27. }
2、删除链表的倒数第n个节点
描述
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，给出的链表为: 1→2→3→4→5, n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.
数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度O(n)
备注：题目保证 n 一定是有效的
1. 示例1 2. 输入： 3. {1,2},2 4. 5. 返回值： 6. {2}
思路描述：首先要判空，否则就没有必要进行下去了。删除链表中结点的操作就比较简单，直接让该结点的前一个结点的next指向该结点的后一个结点即可。本题的关键在于如何找到这个结点，由于是倒数的，所以我们要算出该链表的长度，就写个size函数即可。然后把倒数转化为正着数即可，定义一个newSize=size(head)- n;即可得到正着的结点位置，然后进行删除操作即可！
AC代码：
1. import java.util.*; 2. 3. /* 4. * public class ListNode { 5. * int val; 6. * ListNode next = null; 7. * } 8. */ 9. 10. public class Solution { 11. /** 12. * 13. * @param head ListNode类 14. * @param n int整型 15. * @return ListNode类 16. */ 17. public ListNode removeNthFromEnd (ListNode head, int n) { 18. if(head==null){ 19. return null; 20. } 21. ListNode cur=head; 22. ListNode pre =null; 23. int newSize=size(head)-n; 24. while(cur!=null&&newSize!=0){ 25. pre=cur; 26. cur=cur.next; 27. newSize--; 28. } 29. if(cur!=head){ 30. pre.next=cur.next; 31. }else{ 32. head=cur.next; 33. } 34. 35. 36. return head; 37. 38. } 39. public int size(ListNode head){ 40. int size=0; 41. ListNode cur=head; 42. while(cur!=null){ 43. cur=cur.next; 44. size++; 45. } 46. return size; 47. } 48. }
3、判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0≤n≤10^5，链表中每个节点的值满足 ∣val∣≤10^7
1. 示例1 2. 输入： 3. {1} 4. 5. 返回值： 6. true 7. 8. 示例2 9. 输入: 10. {2,1} 11. 12. 返回值： 13. false 14. 15. 说明： 16. 2->1 17. 示例3 18. 输入： 19. {1,2,2,1} 20. 21. 返回值： 22. true 23. 24. 说明： 25. 1->2->2->1
思路描述：回文数我们见的多了，对于链表，我们想知道是不是回文数，经常使用双指针来解决。这题的关键在于找到中间结点，然后将中间结点后面的结点进行反转，反转完了之后分别从两端开始进行比较，直到出现不相等为止，如果没有不相等的，就是回文，有不相等的就不是回文。主要思想就是定义一个快指针，一个慢指针，快的一次走两步，慢的一次走一步，当快的走到链表的尾结点的时候，慢的就是中间结点的位置，然后把它后面的结点进行反转，上面说过怎么反转了，最后，从两端开始比较即可！
AC代码：
1. import java.util.*; 2. 3. /* 4. * public class ListNode { 5. * int val; 6. * ListNode next = null; 7. * } 8. */ 9. 10. public class Solution { 11. /** 12. * 13. * @param head ListNode类 the head 14. * @return bool布尔型 15. */ 16. public boolean isPail (ListNode head) { 17. // write code here 18. if(head==null){ 19. return true; 20. } 21. if(head.next==null){ 22. return true; 23. } 24. 25. 26. ListNode slow=head; 27. ListNode fast=head; 28. 29. while(fast!=null&&fast.next!=null){ 30. 31. fast=fast.next.next; 32. slow=slow.next; 33. 34. } 35. 36. ListNode cur=slow.next; 37. while(cur!=null){ 38. 39. ListNode curNext=cur.next; 40. cur.next=slow; 41. slow=cur; 42. cur=curNext; 43. } 44. 45. while(head!=slow){ 46. if(head.val!=slow.val){ 47. return false; 48. } 49. if(head.next==slow){ 50. return true; 51. } 52. head=head.next; 53. slow=slow.next; 54. } 55. return true; 56. } 57. }
